[Baekjoon] 1600번 말이 되고픈 원숭이 (Java) 문제 풀이 [Gold 3]

문제

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

1600번: 말이 되고픈 원숭이

 

어떻게 풀 것인가?

문제를 읽었을 때, 빠르게 BFS를 떠올렸다.

하지만 문제는 말의 이때 단순히 visited배열을 2차원으로 선언해 주면 인접 노드로 이동했을 때와 말이 이동할 수 있는 위치로 이동했을 때 서로 다른 경로로 방문했지만 이를 구별할 수 없어 무조건 한번 방문한 곳은 다시 방문할 수 없다는 점을 발견했다.

 

그래서 이 부분에 대해서 골똘히 고민을 하다가 결국엔 다른 분의 풀이를 읽고 단순하게 3차원 배열로 구분하여 문제를 풀이할 수 있었다.

 

이 부분을 제외하면 정석적인 BFS 문제의 풀이였다.

 

풀면서 놓쳤던점

말과 원숭이의 경로 방문이 겹쳐서 한번 방문한 장소를 2번 이상 방문하지 못한다는 점

 

이 문제를 통해 얻어갈 것

BFS의 visit 배열의 응용

 

내 코드 

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

class Main {
    static int K;
    static int W, H;
    static int[][] map;

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    static int[] horseX = {2, 1, -1, -2, 2, 1, -1, -2};
    static int[] horseY = {1, 2, 2, 1, -1, -2, -2, -1};

    static boolean[][][] visit;

    static int result = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        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());
            }
        }
        visit = new boolean[H][W][K + 1];

        BFS(0, 0);
        System.out.println(result);

    }

    private static void BFS(int x, int y) {
        visit[x][y][K] = true;
        Queue<Node> que = new LinkedList<>();
        que.offer(new Node(x, y, 0, K));

        while (!que.isEmpty()) {
            Node cur = que.poll();
            int k = cur.K;

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                int dir = cur.dir;

                if (range(nx, ny) && !visit[nx][ny][k] && map[nx][ny] != 1) {
                    visit[nx][ny][k] = true;
                    que.offer(new Node(nx, ny, dir + 1, k));
                }
            }

            if (k > 0) {
                for (int i = 0; i < 8; i++) {
                    int nx = cur.x + horseX[i];
                    int ny = cur.y + horseY[i];
                    int dir = cur.dir;
                    if (range(nx, ny) && !visit[nx][ny][k-1] && map[nx][ny] != 1) {
                        visit[nx][ny][k-1] = true;
                        que.offer(new Node(nx, ny, dir + 1, k - 1));
                    }
                }
            }

            if (cur.x == H - 1 && cur.y == W - 1) {
                result = cur.dir;
                break;
            }
        }
    }

    private static boolean range(int x, int y) {
        return 0 <= x && x < H && 0 <= y && y < W;
    }

}

class Node {
    int x;
    int y;
    int dir;

    int K;

    Node(int x, int y, int dir, int K) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.K = K;
    }
}

 

참고

https://moonsbeen.tistory.com/181

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