백준 1600. 말이 되고픈 원숭이 :: 돼지개발자

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

"나이트 처럼 갈 수 있는 이동이 중요한 BFS"

처음에 해당 문제를 그냥 최단거리를 구하는것 처럼 int[][] visited 배열을 두어 최대값으로 세팅하고, 특정 위치에서 최소가 되는 경우만 탐색을 진행하도록 했다. 여기서 간과한 것이... 특정위치에 나이트를 한번 쓰고 온 것과 안 쓰고 온 것은 다르다는 것이다. 

아래와 같은 경우를 보자. 먼저 나이트 이동으로 (0,0) 에서 (1,2) 로 이동해서 visited[1][2] = 1 (이동횟수) 이 된다고 하면, 원숭이의 걸음으로 3번 이동해서 온 경우는 더이상 탐색을 하지 못하게 된다. (이미 최소 크기로 해당경로를 지나갔기 때문에..) 정상적이라면 최단 거리는 4가 되지만, 이런 식으로 구한다면, 정답은 -1이 나온다.

1

4 4

0 0 0 1

1 1 0 1

1 1 1 1

1 1 1 0

따라서, 위에서도 언급했듯이 특정 위치 x,y에 가능한 나이트 횟수가 1이냐 0이냐 3이냐는 다르다. 이를 체크해주는 3차원 boolean 배열을 이용한다.

visited[행][열][가능한 나이트 이동의 개수K]

이 배열을 이용해서 방문 체크를 하도록 하고, BFS를 돌린다. 잘 생각하고 문제를 풀어야겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
    
    static int K;
    static int W,H;
    static int[][] map;
    static boolean[][][] visited;
    static Queue<Node> q = new LinkedList<>();
    static int[] dx = {0,0,1,-1,-2,-1,1,2,2,1,-1,-2};
    static int[] dy = {1,-1,0,0,1,2,2,1,-1,-2,-2,-1};
    
    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());
                
        map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        visited[0][0][K] = true;
        q.add(new Node(0, 0, K));
        int cnt = 0;
        boolean ok = false;
        
        loop :while(!q.isEmpty()) {
            int size = q.size();
            
            for (int s = 0; s < size; s++) {
                Node cur = q.poll();
                
                if(cur.x == H-1 && cur.y == W-1) {
                    ok = true;
                    break loop;
                }
                
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];
                    
                    if(!isRange(nx, ny) || visited[nx][ny][cur.horse] || map[nx][ny] == 1)
                        continue;
                    
                    visited[nx][ny][cur.horse] = true;
                    q.add(new Node(nx, ny, cur.horse));
                }
                
                if(cur.horse > 0) {
                    for (int i = 4; i < 12; i++) {
                        int nx = cur.x + dx[i];
                        int ny = cur.y + dy[i];
                        
                        if(!isRange(nx, ny) || visited[nx][ny][cur.horse-1] || map[nx][ny] == 1)
                            continue;
                        
                        visited[nx][ny][cur.horse-1] = true;
                        q.add(new Node(nx, ny, cur.horse-1));
                    }    
                }
            }
            cnt++;
        }
        System.out.println(ok ? cnt : -1);
        
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= H || y < 0 || y >= W) return false;
        return true;
    }
}
 
class Node {
    int x;
    int y;
    int horse;
    Node (int x, int y, int horse) {
        this.x = x;
        this.y = y;
        this.horse = horse;
    }
}