🙋 BFS 이용!
레벨:2
BFS 문제를 오랜만에 풀어서 그런지, BFS인게 감은 오는데 어떻게 풀어야할지 모르겠더라.
다른사람들의 풀이(코드말고)를 보고 짰다.
내가 처음에 기억 못하고 놓쳐서 헤맸던 부분은 이거다.
큐에 어떤 값을 넣어야하나?
보통 사방으로 이동하면서 해당 값을 넣는데, 여기서는 어떤값을 넣어야할까?
그래프라서 그 위치를 표현하는 y,x의 좌표를 넣는다.
그런데, 거리까지 측정하라했으니 거리를 나타내는 변수까지 같이 넣겠다.
이 정보를 담은 내부 클래스를 만들겠다.
이렇게 생각하니 단번에 해결됐다.
Troubleshooting
문제
상대 팀 진영에 도착할 수 없는 경우의 결과만 -1로 잘 나오고, 도착할 수 있는 경우에는 최단 거리가 나오는게 아니라 그 테스트케이스에서도 -1이 나온다.
원인
또또... 그래프에서 [x][y]라고 표현했다...
아니 행이 y이고 열이 x라고 사용하기로해놓고 중간에 계속 [x][y]라 쓰고있었다..
해결
[y][x]로 순서를 변경했다.
제출 코드
import java.util.*;
class Solution {
static int[] dy = {0,1,0,-1};
static int[] dx = {1,0,-1,0};
static boolean[][] visited;
public class Info {
int x;
int y;
int depth;
public Info(int x, int y,int depth) {
this.x =x;
this.y= y;
this.depth = depth;
}
}
public int solution(int[][] maps) {
visited = new boolean[maps.length][maps[0].length];
return bfs(maps.length, maps[0].length, maps);
}
public int bfs(int n, int m, int[][] maps) {
Queue<Info> q = new LinkedList<>();
q.add(new Info(0,0,1));
visited[0][0] = true;
while(!q.isEmpty()) {
Info here = q.poll();
for(int i=0; i<4; i++) {
int nextX = here.x + dx[i];
int nextY = here.y + dy[i];
if(nextX >= 0 && nextY < n && nextY >= 0 && nextX < m) {
if(maps[nextY][nextX] == 0) continue;
if(nextY == n-1 && nextX == m-1) return here.depth+1;
if(!visited[nextY][nextX]) {
q.add(new Info(nextX, nextY, here.depth+1));
visited[nextY][nextX] = true;
}
}
}
}
return -1;
}
}