[PCCP 모의고사 2회] 4번 - 보물지도 (JAVA)

문제 풀러가기

문제 분석

3차원 방문 배열을 사용해야하는 BFS 문제

비슷한 문제로는 백준에
말이 되고픈 원숭이, 벽 부수고 이동하기 가 있다!

---

풀이 방법

신발을 신었을 때 이동할 수 있는 거리가 다르니, dx dy 배열을 잘 생성해주고 BFS를 돌려주면 된다

신발을 신고 이동하는게 남았을 때 이동해주고 방문 체크

3차원 방문 배열은 신발을 신고 이동한 횟수 cnt로 체크해주기

신발 신고 이동 시 visit 조건 탐색은 cur.use+1로 해주는 거 잊지말기!

마지막에 종료 조건인 보물에 도착하면
BFS 특징으로, 가장 먼저 도착한게 가장 빠른것이므로 return 해주기

---

내 코드

import java.util.*;

class Solution {
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,-1,0,1};
    static int[] dx2 = {-2,0,2,0};
    static int[] dy2 = {0,-2,0,2};
    
    static class Data {
        int x, y, use, time;
        public Data(int x, int y, int use, int time) {
            this.x = x;
            this.y = y;
            this.use = use;
            this.time = time;
        }
    }
    
    static int N, M, answer;
    static boolean[][] map;
    static boolean[][][] visit;
    public int solution(int n, int m, int[][] hole) {
        N = m;
        M = n;
        map = new boolean[N][M];
        for(int i = 0; i<hole.length; i++) {
            int a = N-hole[i][1];
            int b = hole[i][0]-1;
            map[a][b] = true;
        }
        
        answer = -1;
        visit = new boolean[N][M][2];
        bfs(N-1, 0);
        //보물 위치는 0,M-1
        return answer;
    }
    
    private static void bfs(int x, int y) {
        visit[x][y][0] = true;
        Queue<Data> q = new ArrayDeque<>();
        q.offer(new Data(x, y, 0, 0));
        
        while(!q.isEmpty()) {
            Data cur = q.poll();
            //System.out.println(cur.x + " " + cur.y + " " + cur.use + " " + cur.time);
            if(cur.x == 0 && cur.y == M-1) {
                answer = cur.time;
                return;
            }
            
            for(int k = 0; k<4; k++) {
                int nx = cur.x+dx[k];
                int ny = cur.y+dy[k];
                
                if(nx>=0 && nx<N && ny>=0 && ny<M && !visit[nx][ny][cur.use]) {
                    if(!map[nx][ny]) { //함정 칸이 아니라면
                        visit[nx][ny][cur.use] = true;
                        q.offer(new Data(nx, ny, cur.use, cur.time+1));
                    }
                }
            }
            
            //아직 신발을 사용하지 않았다면
            if(cur.use == 0) {
                for(int k = 0; k<4; k++) {
                   int nx = cur.x+dx2[k];
                    int ny = cur.y+dy2[k];
                    
                    if(nx>=0 && nx<N && ny>=0 && ny<M && !visit[nx][ny][cur.use+1]) {
                        if(!map[nx][ny]) {
                            visit[nx][ny][cur.use+1] = true;
                            q.offer(new Data(nx, ny, cur.use+1, cur.time+1));   
                        }
                    }
                }
            } 
        } 
    }
}

프로그래머스는 디버깅이 참 힘들다.. 많은 연습 필요!