N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
첫째 줄에 최소 이동 칸의 개수를 출력한다.
5 6
101010
111111
000001
111111
111111
10
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// Queue 에 사용될 Node 클래스
class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
/* Getter 메소드 */
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
}
public class dfs_bfs_02 {
public static int n, m;
public static int[][] graph = new int[201][201];
// 이동방향 정의
public static int[] dx = {-1, 1, 0, 0};
public static int[] dy = {0,0,-1,1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// n, m 입력
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
// 그래프 초기화
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
graph[i][j] = str.charAt(j) - '0';
}
}
// BFS 수행 결과 출력
System.out.println(bfs(0, 0));
}
public static int bfs(int x, int y) {
// Queue 구현을 위해 Queue 라이브러리 사용
Queue<Node> q = new LinkedList<Node>();
q.offer(new Node(x, y));
// 큐가 빌 때 까지
while(!q.isEmpty()) {
Node node = q.poll();
x = node.getX();
y = node.getY();
// 4 방향 확인
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 범위 밖인 경우
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
// 괴물(벽)이 존재하는 경우
if (graph[nx][ny] == 0) {
continue;
}
// 이동 가능한 경우
if (graph[nx][ny] == 1) {
graph[nx][ny] = graph[x][y] + 1;
q.offer(new Node(nx, ny));
}
}
}
// 탈출구(우측 최하단 위치)까지의 최단거리 반환
return graph[n-1][m-1];
}
}