BOJ1600_말이 되고픈 원숭이

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

문제정리

1. 말은 체스의 나이트와 같은 이동방식을 가진다.

2. 말은 장애물을 뛰어넘을 수 있다.

3. 원숭이는 총 K번만 말과 같은 움직임을 할 수 있다. 그 외에는 인접한 칸으로만 움직일 수 있다.(상,하,좌,우)

4. map의 맨 왼쪽 위에서 맨 오른쪽 아래까지 가야한다. 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로

도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.

5. map[H][W] 이다. 장애물이 있는 곳으로는 이동할 수 없다.

문제issue

1. 처음에는 최소라서 BFS라고 생각했지만 한 셀에서 원숭이로 갈 수 있는 경우 , 말로 갈 수 있는 경우를 모두

살펴봐야 해서 DFS로 해야겠다고 생각했지만 결론은 최소 = BFS 이다.

2. BFS를 사용하여 한 셀에서 원숭이로 최대 4방향 , 말로 최대 8방향을 가는 경우를 모두 살펴볼 것인가??

- 객체 큐에 위치 , 몇번 움직였는지 cnt , 말의 움직임 기회 k를 가지고 다녀야 한다.

또한, visited를 체크할 때 3차원을 이용해서 말의 움직임을 사용했는지 까지 체크를 해준다.

visited를 3차원을 사용하면 특정 셀에서 원숭이로 올 수 있는 경우와 말을 한 번 사용하고 원숭이로 오는 경우가

다른 움직임으로 처리해서 정확한 visited체크를 할 수 있다.

해결흐름

1. visited[K+1][H][W]로 map[H][W]로 선언해준다.

2. 처음 위치에서 큐에 add해주고 visited의 3차원 모든 값에 true 처리 해준다.

3. 큐에 있는 값에서 말의 기회가 있다면 말의 움직임으로 살펴본다.

(1) 말의 dh = {-2,-2,-1,1,2,2,1,-1} , dw = {-1,1,2,2,1,-1,-1,-1} 이다.

(2) 범위 안이고 장애물이 아니고 visited[k-1][nh][nw] = false이면 말의 움직임으로 갈 수 있는 셀이므로 이동한 뒤

움직임을 나타내는 cnt++ , 말의 움직임 기회를 나타내는 horse-- 해준 뒤 큐에 넣어주고 visited 체크 해준다.

(3) nh == H - 1 이고 nw = W - 1이면 도착지점에 도착했으니 min_cnt 값을 갱신해주고 끝내준다.

4. 말의 움직임이 있든 없든 모든 셀에서 원숭이의 움직임은 다 살펴야 하기 때문에 원숭이의 움직임 조건에는 말의

움직임 기회가 영향을 주지 않는다.

(1) 말의 움직임과 비슷하다. 말의 기회인 horse만 변화를 주지말고 큐에 넣어준다.

5. while(!q.isEmpty)를 돌다가 도착지점에 못가는 경우라면 갈 수 없는 경우이므로 -1을 출력하고 끝낸다.

소스코드

x
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
​
public class Main {
​
    private static int K;
    private static int W;
    private static int H;
    private static int[][] map;
    private static boolean[][][] visited;
    private static int min_cnt;
    private static int[] h_dh = { -2, -2, -1, 1, 2, 2, 1, -1 };
    private static int[] h_dw = { -1, 1, 2, 2, 1, -1, -2, -2 };
    private static int[] m_dh = { -1, 1, 0, 0 };
    private static int[] m_dw = { 0, 0, 1, -1 };
​
    static class pair {
        int h;
        int w;
        int cnt;
        int horse;
​
        public pair(int h, int w, int cnt, int horse) {
            super();
            this.h = h;
            this.w = w;
            this.cnt = cnt;
            this.horse = horse;
        }
    }
​
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new int[H][W];
        visited = new boolean[K + 1][H][W];
        for (int h = 0; h < H; h++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int w = 0; w < W; w++) {
                map[h][w] = Integer.parseInt(st.nextToken());
            }
        }
        min_cnt = 0;
        bfs(0, 0, 0, K);
        System.out.println(min_cnt);
​
    } // end of main
​
    private static void bfs(int i, int j, int cnt, int k) {
        Queue<pair> q = new LinkedList<pair>();
        q.add(new pair(i, j, cnt, k));
        for (int l = 0; l <= k; l++) {
            visited[l][i][j] = true;
        }
        while (!q.isEmpty()) {
            int q_size = q.size();
            for (int size = 0; size < q_size; size++) {
                pair p = q.poll();
                if (p.horse >= 1) {
                    for (int horse = 0; horse < h_dh.length; horse++) {
                        int h_nh = p.h + h_dh[horse];
                        int h_nw = p.w + h_dw[horse];
                        if (h_nh >= 0 && h_nh < H && h_nw >= 0 && h_nw < W && map[h_nh][h_nw] != 1
                                && !visited[p.horse-1][h_nh][h_nw]) {
                            int cnt2 = p.cnt;
                            cnt2++;
                            int horse2 = p.horse;
                            horse2--;
                            if(h_nh == H-1 && h_nw == W-1) {
                                min_cnt = p.cnt + 1;
                                return;
                            }
                            q.add(new pair(h_nh, h_nw, cnt2, horse2));
                            visited[horse2][h_nh][h_nw] = true;
                        }
                    }
                }
                for (int monkey = 0; monkey < m_dh.length; monkey++) {
                    int m_nh = p.h + m_dh[monkey];
                    int m_nw = p.w + m_dw[monkey];
                    if (m_nh >= 0 && m_nh < H && m_nw >= 0 && m_nw < W && map[m_nh][m_nw] != 1
                            && !visited[p.horse][m_nh][m_nw]) {
                        int cnt2 = p.cnt;
                        cnt2++;
                        int horse2 = p.horse;
                        if(m_nh == H-1 && m_nw == W-1) {
                            min_cnt = p.cnt + 1;
                            return;
                        }
                        q.add(new pair(m_nh, m_nw, cnt2, horse2));
                        visited[horse2][m_nh][m_nw] = true;
                    }
                }
            }
        }
        min_cnt = -1;
        return;
    }
} // end of class