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

 

문제 이해

1,1에서 시작해서 -> n,m까지 도착하는 시간을 적어라

but, 장애물 hole이 있고,

신비로운 신발 하나를 통해 한번은 두칸을 뛰어 넘을 수 있다.

 

알고리즘

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

백준의 말이 되고픈 원숭이가 생각나는 문제였다.

여기서 가장 중요한 것은

visit 방문처리를 할 때, 신비로운 신발 까지 썼는지 안썼는지 체크해서 진행해야한다!

 

코드

import java.util.*;
class Solution {
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    boolean[][][] isVisit;
    int[][] graph;
    public int solution(int n, int m, int[][] hole) {
        int answer = 0;
        graph = new int[n][m];
        isVisit = new boolean[n][m][2];
        for(int[] h: hole){
            graph[h[0] -1 ][h[1] -1 ] = -1;
        }
        answer = BFS(n,m);
        return answer;
    }
    
    public int BFS(int n, int m){
        Queue<int[]> q = new ArrayDeque<>();
        // x, y, 신비신발, 시간;
        q.add(new int[]{0,0,1,1});
        isVisit[0][0][1] = true;
        while(!q.isEmpty()){
            int[] now = q.poll();
            int x = now[0]; int y = now[1]; int shoe = now[2]; int turn = now[3];
            if(x == n-1 && y == m-1){
                return turn - 1;
            }
            for(int i = 0; i< 4; i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(nx < 0 || nx >= n || ny<0 || ny>=m ) continue;
                if(isVisit[nx][ny][shoe]) continue;
                if(graph[nx][ny] == -1) continue;
                q.add(new int[]{nx,ny,shoe,turn+1});
                isVisit[nx][ny][shoe] = true;
            }
            if(shoe == 1){
                int nextShoe = 0;
                for(int i = 0; i < 4; i++){
                    int nx = x + (dx[i]*2);
                    int ny = y + (dy[i]*2);
                    if(nx < 0 || nx >= n || ny<0 || ny>=m ) continue;
                    if(isVisit[nx][ny][nextShoe]) continue;
                    if(graph[nx][ny] == -1) continue;
                    q.add(new int[]{nx,ny,nextShoe,turn+1});
                    isVisit[nx][ny][nextShoe] = true;
                }
            }
        }
        
        return -1;
    }
}