[프로그래머스스쿨] pccp 모의고사 2회 보물지도 4번 java - bfs

문제는 전형적인 bfs 문제이지만 세부 조건을 잘 처리하지 않으면

시간이 오래 소모될 수 있다 ㅜㅜ

나는 다음과 같은 조건을 간과해서 삽질 엄청 했다..;;

 

1. n과 m의 순서 주의

x좌표: 0~m

y좌표: 0~n 이다..

그리고 맨아래 x좌표=0이고 위로 갈수록 x값이 커지는 구조

2. 두번 점프를 할 수도 있고 안 할수도 있음

나는 다익스트라를 이용해서 최소 비용을 갱신하는 식으로 로직을 짰다

이 때에 최소거리(비용)을 나타내는 배열을 삼차원으로 처리해줘야 함

dist[x][y][0] : 두번 점프 안한 경우

dist[x][y][1] : 두번 점프 한 경우

 

 

import java.util.*;
class Solution {
static int[] dx = {0,1,0,-1,0,2,0,-2};
static int[] dy = {1,0,-1,0,2,0,-2,0};
static int[][] graph;
static int[][][] dist;

static int bfs(int x, int y, int n, int m){
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{x,y,0,0});

    while(!q.isEmpty()){
        int[] now = q.poll();
        int nowX = now[0];
        int nowY = now[1];
        int nowC = now[2];
        int nowM = now[3]; //두번 점프 유무

        if(nowX==0&&nowY==m-1){
            continue;
        }

        if(nowM==0){
            for(int i=0;i<4;i++){
                int nextX = nowX+dx[i];
                int nextY = nowY+dy[i];

                if(nextX<0||nextX>=n||nextY<0||nextY>=m) continue;

                if(graph[nextX][nextY]==0 && dist[nextX][nextY][nowM]>nowC+1){
                    dist[nextX][nextY][nowM] = nowC+1;
                    q.add(new int[]{nextX,nextY,nowC+1,nowM});
                }
            }
            //두번 점프
            for(int i=4;i<8;i++){
                int nextX = nowX+dx[i];
                int nextY = nowY+dy[i];

                if(nextX<0||nextX>=n||nextY<0||nextY>=m) continue;

                if(graph[nextX][nextY]==0 && dist[nextX][nextY][1]>nowC+1){
                    dist[nextX][nextY][1] = nowC+1;
                    q.add(new int[]{nextX,nextY,nowC+1,1});
                }
            }
        } else {
            for(int i=0;i<4;i++){
                int nextX = nowX+dx[i];
                int nextY = nowY+dy[i];

                if(nextX<0||nextX>=n||nextY<0||nextY>=m) continue;

                if(graph[nextX][nextY]==0 && dist[nextX][nextY][nowM]>nowC+1){
                    dist[nextX][nextY][nowM] = nowC+1;
                    q.add(new int[]{nextX,nextY,nowC+1,nowM});
                }
            }
        }
    }

    if(dist[0][m-1][0]==Integer.MAX_VALUE&&dist[0][m-1][1]==Integer.MAX_VALUE)
        return -1;
    int answer = Math.min(dist[0][m-1][0],dist[0][m-1][1]);
    return answer;
}

public int solution(int n, int m, int[][] hole) {        
    graph = new int[m][n];
    dist = new int[m][n][2];

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            dist[i][j][0] = Integer.MAX_VALUE;
            dist[i][j][1] = Integer.MAX_VALUE;
        }
    }

    for(int i=0;i<hole.length;i++){
        int holeX = hole[i][0];
        int holeY = hole[i][1];
        graph[m-holeY][holeX-1] = 1;
    }

    return bfs(m-1,0,m,n);
}