문제
https://www.acmicpc.net/problem/16954
풀이
bfs를 이용해 풀었다. 해당 초에서 다음 초에 이동 가능한 경우를 큐에 담고, 벽이 내려가는 함수 drop() 함수를 실행한다. 초마다 맵이 바뀌므로 visited 배열을 초마다 초기화해야 한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[][] board;
public static void main(String args[]) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = 8;
board = new int[N][N];
for (int i = 0; i < N; i++) {
String str = in.readLine();
for (int j = 0; j < N; j++)
board[i][j] = str.charAt(j) == '.' ? 0 : 1;
}
int[][] delta = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 0}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
Queue<int[]> queue = new LinkedList<int[]>();
int sr = 7, sc = 0, er = 0, ec = 7;
queue.offer(new int[] {sr, sc});
int answer = 0;
outer:
while (!queue.isEmpty()) {
int size = queue.size();
boolean[][] visited = new boolean[N][N];
for (int i = 0; i < size; i++) {
int r = queue.peek()[0];
int c = queue.poll()[1];
if (board[r][c] == 1)
continue;
for (int d = 0; d < delta.length; d++) {
int dr = r + delta[d][0];
int dc = c + delta[d][1];
if (dr < 0 || dc < 0 || dr >= N || dc >= N || visited[dr][dc] || board[dr][dc] == 1)
continue;
if (dr == er && dc == ec) {
answer = 1;
break outer;
}
visited[dr][dc] = true;
queue.offer(new int[] {dr, dc});
}
}
drop();
}
System.out.println(answer);
}
static void drop() {
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < N; j++)
board[i + 1][j] = board[i][j];
}
for (int i = 0; i < N; i++)
board[0][i] = 0;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ 백준] 1931 - 회의실 배정, Java(자바) (0) | 2023.03.07 |
---|---|
[BOJ 백준] 12764 - 싸지방에 간 준하, Java(자바) (0) | 2023.03.07 |
[BOJ - 백준] 14923 - 미로탈출, Java(자바) (0) | 2023.03.07 |
[BOJ 백준] 17090 - 미로 탈출하기, Java(자바) (0) | 2023.03.04 |
[BOJ 백준] 1991 - 트리 순회, Java(자바) (0) | 2023.03.04 |