[백준] 1600번 : 말이 되고픈 원숭이

1600번: 말이 되고픈 원숭이

---

[BFS or Dijkstra]

백준 문제 시리즈 중 '벽 뚫고 이동하기'와 비슷한 유형의 문제이다. 최대 k번의 나이트(Knight) 이동을 이용해 (1, 1)에서 (r, c)로 최소한의 이동으로 가는 이동 횟수를 구하는데, 다익스트라나 BFS 둘 다 가능하지만, 다익스트라를 이용한 장점이 없으므로 BFS를 이용한 것이 400ms정도 더 빨랐다. (사실 동일한 코드이고, Queue를 쓰면 BFS, 우선순위 큐를 쓰면 다익스트라로 변신한다.)

 

현재 특정 정점에 도착했을 때, 인접한 곳에 이동할 수 있으면 큐에 넣고, k번 이하로 나이트 이동을 했다면, 나이트 이동으로 갈 수 있는 곳을 나이트 이동으로 이동하며, 그 때의 cnt는 +1 해서 보낸다.

 

public class Main {

    static class Point{
        int y, x, dist, cnt;
        public Point(int yy, int xx, int dist, int cnt){
            y=yy; x=xx;
            this.dist = dist;
            this.cnt = cnt;
        }
    }
    static final int INF = 1000000000;
    static int[][][] dp = new int[201][201][31];
    static int[][] map = new int[201][201];
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1}, Y_ = {2, 1, -1, -2, -2, -1, 1, 2}, X_ = {1, 2, 2, 1, -1, -2, -2, -1};
    static int k, r, c;

    static void BFS(){

        Queue<Point> Q = new LinkedList<>();

        dp[1][1][0] = 0;
        Q.add(new Point(1, 1, 0,0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int dist = p.dist;
            int cnt = p.cnt;

            if(dp[y][x][cnt] < dist) continue;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(nx < 1 || ny < 1 || nx > c || ny > r || map[ny][nx] == 1) continue;

                if(dp[ny][nx][cnt] > dist + 1){
                    dp[ny][nx][cnt] = dist + 1;
                    Q.add(new Point(ny, nx, dist + 1, cnt));
                }
            }
            
            if(cnt < k)
                for(int a=0; a<8; a++){
                    int ny = y+Y_[a];
                    int nx = x+X_[a];

                    if(nx < 1 || ny < 1 || nx > c || ny > r || map[ny][nx] == 1) continue;

                    if(dp[ny][nx][cnt + 1] > dist + 1){
                        dp[ny][nx][cnt + 1] = dist + 1;
                        Q.add(new Point(ny, nx, dist + 1, cnt + 1));
                    }
                }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        c = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        for(int i=1; i<=r; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=c; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                Arrays.fill(dp[i][j], INF);
            }
        }
        
        BFS();
        int min = INF;

        for(int i=0; i<=k; i++)
            if(dp[r][c][i] < min) min = dp[r][c][i];

        System.out.println(min == INF? -1 : min);
    }
}