BOJ#1600 말이 되고픈 원숭이

BOJ#1600 말이 되고픈 원숭이

* 문제

https://www.acmicpc.net/problem/1600

* 풀이

bfs 탐색 문제입니다.

일반적인 격자(상,하,좌,우) 문제에서 말처럼 이동하는 부분이 추가되었다고 생각하면 됩니다.

즉, 각 위치에서 상하좌우(4방향) + 말(8방향) 이렇게 12가지 방향으로 탐색을 진행하면 됩니다.

문제는 중복된 정점을 다시 방문하지 않도록 처리하는 것입니다.

처음에 제가 실수했던 점은 

discovered[row][col][말로 방문한 경우 or 원숭이로 방문한 경우] 로 중복된 정점을 처리했었는데

이것의 반례로 아래의 예가 있습니다.

1

5 5

0 1 1 0 1

0 0 1 0 1

0 0 0 1 1

0 1 0 1 0

1 1 0 1 0

정답 : 6

말의 움직임에 의해 (2,1)에 위치하고, 이어서 (2,1)에서 상하좌우로 움직이는 경우 -> 목적지에 도달할 수 없음

목적지에 도달하려면

원숭이의 움직임에 의해 (3,2)에 위치하고, 이어서 말의 움직임으로 목적지에 도달해야 하는데

이미 위에서 방문 처리가 되었기 때문에 목적지에 도달할 수 없었습니다.

따라서,

discovered 배열을 다음과 같이 변경하여 목적지를 찾을 수 있도록 했습니다.

discovered[row][col][말이 움직인 횟수]

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/07ba7afcf91aa00c2236daae51ff64a39a1f5750/BOJ%231600_horseMonkey/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * BOJ#1600 말이 되고픈 원숭이
 * https://www.acmicpc.net/problem/1600
 */

public class Main {

    static final int BLANK = 0;
    static final int OBSTACLE = 1;

    static final int MONKEY = 0;
    static final int HORSE = 1;

    static final int[] dRowMonkey = {0, -1, 0, 1};
    static final int[] dColMonkey = {-1, 0, 1, 0};

    static final int[] dRowHorse = {-1, -2, -2, -1, 1, 2, 2, 1};
    static final int[] dColHorse = {-2, -1, 1, 2, 2, 1, -1, -2};

    static int K;
    static int W, H;
    static int[][] map = new int[201][201];
    static boolean[][][] discovered = new boolean[201][201][31];

    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());

        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        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());
            }
        }

        int step = -1;
        Queue<Point> queue = new LinkedList<Point>();

        queue.add(new Point(0, 0, K));
        discovered[0][0][MONKEY] = true;
        discovered[0][0][HORSE] = true;

        while (!queue.isEmpty()) {

            step++;

            int size = queue.size();
            for (int i = 0; i < size; i++) {

                Point u = queue.poll();

                if (u.row == H - 1 && u.col == W - 1) {

                    System.out.println(step);
                    return;
                }
                // MONEY
                for (int j = 0; j < 4; j++) {

                    int nextRow = u.row + dRowMonkey[j];
                    int nextCol = u.col + dColMonkey[j];

                    if (nextRow < 0 || nextRow >= H || nextCol < 0 || nextCol >= W) continue;
                    if (discovered[nextRow][nextCol][u.k]) continue;
                    if (map[nextRow][nextCol] == OBSTACLE) continue;

                    queue.add(new Point(nextRow, nextCol, u.k));
                    discovered[nextRow][nextCol][u.k] = true;
                }

                // HORSE
                if (u.k == 0) continue;
                for (int j = 0; j < 8; j++) {

                    int nextRow = u.row + dRowHorse[j];
                    int nextCol = u.col + dColHorse[j];

                    if (nextRow < 0 || nextRow >= H || nextCol < 0 || nextCol >= W) continue;
                    if (discovered[nextRow][nextCol][u.k - 1]) continue;
                    if (map[nextRow][nextCol] == OBSTACLE) continue;

                    queue.add(new Point(nextRow, nextCol, u.k - 1));
                    discovered[nextRow][nextCol][u.k - 1] = true;
                }
            }
        } // ~ while loop

        System.out.println(-1);
    }
}

class Point {

    int row, col;
    int k;

    Point(int row, int col, int k) {

        this.row = row;
        this.col = col;
        this.k = k;
    }
}