Algorithm/이코테
미로 탈출
마닐라
2021. 11. 22. 14:55
import java.util.*;
public class Main {
public static int n;
public static int m;
//미로 정보 담긴 배열인데 거리도 기록할것임
public static int[][] arr;
public static int[] dx = {-1,1,0,0};
public static int[] dy = {0,0,-1,1};
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
m = kb.nextInt();
kb.nextLine();
arr = new int[n][m];
for(int i = 0; i < n; i++) {
String str = kb.nextLine();
for(int j = 0; j < m; j++) {
arr[i][j] = str.charAt(j) - '0';
}
}
System.out.println(Arrays.deepToString(arr));
System.out.println(BFS(0,0));
}
private static int BFS(int x, int y) {
Queue<Point> q = new LinkedList<>();
//첫 좌표 큐에 넣기
q.offer(new Point(x, y));
//큐가 빌때까지 반복하는데 각 좌표마다 거리를 계산한다.
while (!q.isEmpty()) {
Point tmp = q.poll();
x = tmp.x;
y = tmp.y;
//해당 좌표의 상하좌우를 확인해서 이동
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
//이동가능한 곳이고 괴물이 없다면 이동시키기.
if(nx >= 0 && ny >= 0 && nx < n && ny < m && arr[nx][ny] == 1) {
q.offer(new Point(nx, ny));
arr[nx][ny] = arr[x][y] + 1;
}
}
}
return arr[n - 1][m - 1];
}
private static class Point {
public int x;
public int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}