[BOJ] 1600: 말이 되고픈 원숭이 (JAVA)

문제

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

 

여담

예전에 풀었던 문제라 그런지 푸는 방식을 약간 외워서 푼 느낌이다. 비슷한 유형의 문제가 나오면 좋겠지만 그럴 확률은 많지 않으니 다양한 BFS/DFS 문제를 접하도록 노력해야지..!

 

아무튼 이와 같이 기본 조건에 상태에 대한 조건이 추가적으로 있다면 "차원을 추가해서 각각의 상태를 관리"하면 된다는 것을 기억하자!

 

풀이

맨 왼쪽 위에서 맨 오른쪽 아래로 이동하는 최단 거리를 찾는 것이므로 BFS 탐색을 수행하면 된다. 

 

이때, 말처럼 이동하는 횟수에 따라 방문할 수 있는 지점이 달라지므로, 말이 이동한 횟수에 따라 각각 방문 처리를 해줘야 한다. 따라서 방문 처리 배열을 vistied[세로][가로][말처럼 이동한 횟수]와 같이 3차원 배열로 선언해야 한다.

 

문제 풀이 로직은 다음과 같다.

1. 원숭이가 이동할 수 있는 방향(=인접한 네 방향)으로 움직히기
   • 이동 가능한 방향: (1, 0), (-1, 0), (0, 1), (0, -1)
2. 말처럼 이동할 수 있는 횟수가 남았다면 말이 이동하는 방향(=8가지 방향)으로 움직이기
   • 이동 가능한 방향: (2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)
   • 이때, 말처럼 이동한 횟수를 증가시켜야 하므로 방문 처리를 할 때 주의해야 함
     • visited[nx][ny][말처럼 이동한 횟수 + 1] = true

 

코드

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

public class Main {
    static int K, W, H;
    static int[][] board;
    static boolean[][][] visited;
    static int[][] jump = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
    static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) throws Exception {
        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());
        board = new int[H][W];
        visited = new boolean[H][W][K + 1];

        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < W; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(bfs());
    }

    static int bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0, 0, 0));
        visited[0][0][0] = true;

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            int x = now.x, y = now.y;
            if (x == H - 1 && y == W - 1) {
                return now.dist;
            }

            // 우선 원숭이처럼 이동하기
            for (int i = 0; i < 4; i++) {
                int nx = x + move[i][0];
                int ny = y + move[i][1];
                if (nx < 0 || ny < 0 || nx >= H || ny >= W || visited[nx][ny][now.jump]) {
                    continue;
                }

                if (board[nx][ny] == 0) { // 평지면 이동 가능
                    queue.offer(new Node(nx, ny, now.jump, now.dist + 1));
                    visited[nx][ny][now.jump] = true;
                }
            }

            // 말처럼 이동할 수 있는 횟수가 남은 경우
            if (now.jump < K) {
                for (int i = 0; i < 8; i++) {
                    int nx = x + jump[i][0];
                    int ny = y + jump[i][1];
                    if (nx < 0 || ny < 0 || nx >= H || ny >= W || visited[nx][ny][now.jump + 1]) {
                        continue;
                    }

                    if (board[nx][ny] == 0) { // 평지면 이동 가능
                        queue.offer(new Node(nx, ny, now.jump + 1, now.dist + 1));
                        visited[nx][ny][now.jump + 1] = true;
                    }
                }
            }
        }
        return -1;
    }

    static class Node {
        int x, y;
        int jump; // 말처럼 움직인 횟수
        int dist; // 이동 횟수

        public Node(int x, int y, int jump, int dist) {
            this.x = x;
            this.y = y;
            this.jump = jump;
            this.dist = dist;
        }
    }
}

---