백준 1600번 말이 되고픈 원숭이 G3 - BFS

진짜임 오늘 1병만 마셨어여

 

 

 

아오 아ㅣ오아오 1시간 20분 걸렸다.

 

이전 문제인 벽 부수면서 이동하기 

백준 2206번 벽 부수고 이동하기 G3 - BFS

와 비슷한 유형이다.

 

탐색 조건이 추가되어서 3차원 배열이나 다른 조건으로 Visited로 체크를 해야한다.

일반적인 방향 탐색 + 조건이 있는 방향으로 탐색해야 할때 중복되는 경우를 체크해야 하기 때문이다.

 

 

체스 나이트 형태로 이동할 수 있는 케이스를 체크해서 중복이 없도록 확인해야 한다.

 

import java.io.*;
import java.util.*;
 
public class Main { // Boj_1600_말이 되고픈 원숭이
 
    static class Monkey {
        int x, y, dist, left_horse_step;
 
        public Monkey(int x, int y, int dist, int left_horse_step) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.left_horse_step = left_horse_step;
        }
    }
 
    static int H, W, answer, K;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int[][] monkey_step = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}};
    static int[][] map;
    static boolean[][][] visit;
 
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        answer = -1;
        K = Integer.parseInt(st.nextToken());
        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());
            }
        }
        answer = bfs(0, 0);
        System.out.println(answer);
    }
 
    public static int bfs(int x, int y) {
        visit = new boolean[H][W][K + 2];
        Queue<Monkey> que = new ArrayDeque<>();
        que.offer(new Monkey(x, y, 0, 0));
        visit[x][y][0] = true; // 말 스텝 체크
        // 벽 부수기와 동일, 말이 스텝한곳을 따로 체크해야 일반 원숭이 스텝도 체킹 가능.
 
        while (!que.isEmpty()) {
            Monkey cur = que.poll();
            if (cur.x == H - 1 && cur.y == W - 1) {
                return cur.dist; // 한번에 도착하는 경우도 체크하려고
            }
 
            for (int i = 0; i < 4; i++) { // 일반 원숭이
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (range_chk(nx, ny) && map[nx][ny] != 1 && !visit[nx][ny][cur.left_horse_step]) { // 아 visit 조건 ㅡㅡ
                    que.add(new Monkey(nx, ny, cur.dist + 1, cur.left_horse_step));
                    visit[nx][ny][cur.left_horse_step] = true;
                }
            }
            if (cur.left_horse_step < K) { // 말 스텝
                for (int i = 0; i < 8; i++) {
                    int nx = cur.x + monkey_step[i][0];
                    int ny = cur.y + monkey_step[i][1];
                    if (range_chk(nx, ny) && map[nx][ny] != 1 && !visit[nx][ny][cur.left_horse_step+1]) {
                        que.add(new Monkey(nx, ny, cur.dist + 1, cur.left_horse_step + 1));
                        visit[nx][ny][cur.left_horse_step + 1] = true;
                    }
                }
            }
        }
        return -1;
    }
 
    public static boolean range_chk(int x, int y) {
        return 0 <= x && 0 <= y && x < H && y < W;
    }
}

 

아오 오래걸렸다리 ㅋ 술먹고 풀어서 그런가