[BOJ/Java] 1600. 말이 되고픈 원숭이

[BOJ/Java] 1600. 말이 되고픈 원숭이

1600번: 말이 되고픈 원숭이

---

문제 설명

본 문제에서는 격자 위에서 원숭이가 말의 이동 방식을 제한된 횟수 안에서 사용할 수 있으며, 최소 이동 횟수로 목적지에 도달해야 한다. 격자의 각 칸은 빈 공간이거나 벽일 수 있다. 원숭이는 기본적인 상하좌우 이동 외에도 말처럼 이동할 수 있는 기능을 제한적으로 사용할 수 있다.

풀이 과정

• 데이터 입력과 초기화: 맵의 크기와 말처럼 이동할 수 있는 최대 횟수를 입력받는다. 맵의 각 칸에 대한 정보를 입력받아 장애물과 빈 공간을 구분한다.
• 너비 우선 탐색(BFS)의 적용: 원숭이의 시작 위치에서 BFS를 시작하여, 가능한 모든 경로를 탐색한다. 각 위치에서 원숭이는 일반 이동과 말의 이동을 선택할 수 있다.
• 이동 검증: 이동할 때마다 해당 위치가 벽이 아니고 맵의 범위 내에 있는지 확인한다.
• 결과 출력: 목적지에 도달하는 최소 이동 횟수를 계산하여 출력한다. 만약 도달할 수 없는 경우 -1을 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No1600;

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

public class Main {
    private int k, w, h; // k는 말처럼 움직일 수 있는 최대 횟수, w와 h는 맵의 너비와 높이
    private int[][] map; // 맵의 정보를 저장할 배열
    // 말의 이동 방식을 정의한 배열
    private static final int[][] horseDirection = { 
        { -2, -1 }, { -2, 1 }, { -1, -2 }, { -1, 2 }, { 1, -2 }, { 1, 2 }, { 2, -1 }, { 2, 1 } 
    };
    // 기본 상하좌우 이동을 정의한 배열
    private static final int[][] direction = { 
        { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } 
    };

    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(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()); // 맵 정보 입력
            }
        }

        int ans = bfs(); // BFS를 통해 최단 이동 횟수 계산

        System.out.println(ans); // 결과 출력
    }

    private int bfs() {
        Queue<Point> queue = new ArrayDeque<>(); // BFS 수행을 위한 큐
        boolean[][][] visited = new boolean[h][w][k + 1]; // 방문 관리를 위한 3차원 배열
        queue.offer(new Point(0, 0, 0, 0)); // 시작점 큐에 추가
        visited[0][0][0] = true; // 시작점 방문 처리

        while (!queue.isEmpty()) {
            Point p = queue.poll(); // 큐에서 원소를 하나 꺼냄

            if (p.x == h - 1 && p.y == w - 1) return p.cnt; // 목적지에 도달한 경우 이동 횟수 반환

            // 기본 이동 수행
            for (int d = 0; d < direction.length; d++) {
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];
                if (!isValid(nx, ny) || visited[nx][ny][p.k]) continue;
                visited[nx][ny][p.k] = true;
                queue.offer(new Point(nx, ny, p.cnt + 1, p.k));
            }

            // 말처럼 이동 가능한 경우 추가 이동 수행
            if (p.k < k) {
                for (int hd = 0; hd < horseDirection.length; hd++) {
                    int nx = p.x + horseDirection[hd][0];
                    int ny = p.y + horseDirection[hd][1];
                    if (!isValid(nx, ny) || visited[nx][ny][p.k + 1]) continue;
                    visited[nx][ny][p.k + 1] = true;
                    queue.offer(new Point(nx, ny, p.cnt + 1, p.k + 1));
                }
            }
        }

        return -1; // 목적지에 도달할 수 없는 경우 -1 반환
    }

    // 맵 내에 위치하며 벽이 아닌 위치인지 확인하는 메소드
    private boolean isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < h && y < w && map[x][y] != 1;
    }

    // 위치와 이동 횟수, 말처럼 움직인 횟수를 저장하는 클래스
    class Point {
        int x, y, cnt, k;

        public Point(int x, int y, int cnt, int k) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.k = k;
        }
    }
}

시간 복잡도 분석

이 알고리즘은 BFS를 활용하여 각 위치에 대해 가능한 모든 이동 경로를 검토한다. 각 위치에서는 최대 12개의 가능한 이동이 있으므로, 시간 복잡도는 O(12×w×h×(k+1))이다. 이는 모든 가능한 상태를 고려한 복잡도로, 매우 높을 수 있다.

느낀점

이 문제는 다양한 이동 옵션과 제한된 자원을 활용하여 최적의 결과를 도출하는 전략적인 접근이 요구된다. BFS와 함께 다차원 방문 배열을 사용하여 상태 공간을 관리하는 방식은 복잡한 탐색 문제에 매우 유용하다.