[골드3, BFS] 백준 1600 - 말이 되고픈 원숭이 (자바)

Think

1. 4방탐색과 말 움직임을 구현하는건 어렵진 않았다. 다만 오른쪽 아래까지 가는 최단거리를 어떻게 구할지가 고민이었다.
2. 처음에는 무조건 말 움직임으로 가는것이 최단거리이지 않을까 생각했다.
3. 하지만, 탐색하려는 특정 정점까지의 최단거리는 무조건 말 움직임으로 갈때만이 최단 거리가 아니다.
   • 1
     5 5
     00010
     00010
     00110
     01110
     00000
   • 예를들어, 위의 인풋이 들어왔을떄, [5,2]까지 가는 최단거리는 3가지 방법이 있다.
   • 4방탐색으로만 가기 (6번) / 말 움직임 먼저 간 후[2,1], 4방탐색으로 가기 (6번) / 4방탐색으로 먼저 간 후[2,1], 말 움직임으로 가기 (4번) 
   • 그렇기 때문에, 그리디로 풀수는 없고 완탐으로 풀어야된다는 생각을 했다.
   • https://yabmoons.tistory.com/48 에서도 잘 설명되어있다.
4. BFS를 여러번해서는 시간초과가 날 수 있기때문에, 한번의 BFS로 해야한다는 생각이 들었고, 백준 2206 - 벽 부수고 이동하기 문제를 풀때의 방법이 생각나서 이 방법으로 풀었다.
5. 99%정도에서 틀렸길래 예외를 생각해봤는데, W와 H가 1로 들어올수있다. 그렇기때문에 이 경우를 예외처리 해주자.

 

 

 

내 정답 코드

import java.util.*;
import java.io.*;

public class test {
    static int K, W, H, map[][], result;
    static boolean isVisited[][][];
    static int[] dr = new int[]{0, 0, 1, -1};
    static int[] dc = new int[]{1, -1, 0, 0};
    static int[] horseDr = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] horseDc = new int[]{1, 2, 2, 1, -1, -2, -2, -1};

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();

        process();

        if(result == 0) {
            if(W == 1 && H == 1) System.out.println(0);
            else System.out.println(-1);
        }
        else System.out.println(result);
    }

    private static void process() {

        bfs();

    }

    private static void bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        isVisited = new boolean[K+1][H][W];

        q.add(new int[]{0, 0, 0, 0});
        isVisited[0][0][0] = true;

        while (!q.isEmpty()) {
            int[] currentPosition = q.poll();

            if (currentPosition[0] == H - 1 && currentPosition[1] == W - 1) {
                result = currentPosition[3];
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nextR = currentPosition[0] + dr[i];
                int nextC = currentPosition[1] + dc[i];
                int nextSpendK = currentPosition[2]; // 4방탐색일때는 K사용X
                int nextMoveCount = currentPosition[3] + 1;

                if (nextR < 0 || nextC < 0 || nextR >= H || nextC >= W || isVisited[nextSpendK][nextR][nextC]) continue;
                if(map[nextR][nextC] == 1) continue;

                q.add(new int[]{nextR, nextC, nextSpendK, nextMoveCount});
                isVisited[nextSpendK][nextR][nextC] = true;
            }

            for (int i = 0; i < 8; i++) {
                int nextR = currentPosition[0] + horseDr[i];
                int nextC = currentPosition[1] + horseDc[i];
                int nextSpendK = currentPosition[2] + 1;
                int nextMoveCount = currentPosition[3] + 1;

                if (nextSpendK >= K+1) continue;
                if (nextR < 0 || nextC < 0 || nextR >= H || nextC >= W || isVisited[nextSpendK][nextR][nextC]) continue;
                if(map[nextR][nextC] == 1) continue;

                q.add(new int[]{nextR, nextC, nextSpendK, nextMoveCount});
                isVisited[nextSpendK][nextR][nextC] = true;
            }
        }
    }

    private static void init() throws IOException {
        K = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        map = new int[H][W];

        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < W; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}