문제 바로가기

나의 풀이

처음 풀었을 때는 depth와 remain을 각각의 static 변수로 선언하고, bfs 메서드 내에서 경우를 분기하여 더하고 빼고 확인하는 과정을 거쳤었다.
다만 그 풀이는 메모리 초과가 났다.

결국 이 문제의 요지는 visited에서 한칸씩 앞뒤로 움직이는 방문은 continue하되, 앞서나간 '말' 이동이 거친 경로에 있는 장소를 한칸씩 움직인 경로가 도착하면 그 방문은 continue하면 안된다는 것이다.

그렇게 하기 위해서는 visited 배열을 3차원인 visited[x][y][remain]으로 선언해야한다.

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

// 하나의 이동경로에 의한 좌표 x,y와 이동 횟수 depth, 남은 '말' 이동횟수 remain
class Point {
    public int x;
    public int y;
    public int depth;
    public int remain;

    public Point(int x, int y, int depth, int remain) {
        this.x = x;
        this.y = y;
        this.depth = depth;
        this.remain = remain;
    }
}

class Main {

    static int k, row, col;
    //이 문제에서 가장 중요한 부분
    //단순히 그 좌표지점에 방문했었는지가 중요한게 아니라 그 방문지점에 remain이 같게 도착했느냐가 관건이다
    static boolean[][][] visited;
    static int[][] map;
    static Queue<Point> q;
    static int[] dx = {1,0,-1,0,2,2,1,1,-1,-1,-2,-2};
    static int[] dy = {0,-1,0,1,1,-1,2,-2,2,-2,1,-1};
    
    public static void main(String[] args) throws IOException {

        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        col = Integer.parseInt(st.nextToken());
        row = Integer.parseInt(st.nextToken());

        visited = new boolean[row][col][31];
        map = new int[row][col];
        q = new LinkedList<>();

        for (int i = 0; i < row; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st2.nextToken());
            }
        }

        //logic
        q.offer(new Point(0,0, 0, k));
        int result = bfs();

        //output
        System.out.println(result);
    }

    public static int bfs() {
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Point po = q.poll();
                int x = po.x;
                int y = po.y;
                int depth = po.depth;
                int remain = po.remain;

                // 범위 벗어난 경우
                if (x < 0 || y < 0 || x >= row || y >= col) {
                    continue;
                }
                // 장애물 만난 경우
                if (map[x][y] == 1) {
                    continue;
                }
                // 오른쪽 하단에 도착한 경우 depth 반환
                if (x == row-1 && y == col-1) {
                    return depth;
                }
                // 이 지점에 들린게 문제가 아니라, 같은 remain을 가지고 들렸는지 체크
                if (visited[x][y][remain]) {
                    continue;
                }
                // 방문 기록
                visited[x][y][remain] = true;
                // 한칸씩 움직이는 경우이므로 depth만 더해짐
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    q.offer(new Point(nx, ny, depth + 1, remain));
                }
                // '말' 이동 횟수가 0이면 continue
                if (remain == 0) continue;
                // '말' 이동 횟수가 남았으면 이동시키고 depth는 +1, remain은 -1
                for (int j = 4; j < 12; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    q.offer(new Point(nx, ny, depth + 1, remain - 1));
                }
            }
        }
        return -1;
    }
}