PCCP 모의고사 2회 - 보물 지도

1. 문제 정의

2. 문제 접근

bfs로 접근해서 풀면 될 것 같다.

3. 문제 풀이

1. 지도를 matrix로 표기한다.

2. hole의 위치를 matrix 위에 표기한다.

3. bfs를 돌면서 칸마다 최소 이동 횟수를 표기한다.

4. 정답을 return한다.

 

4. 코드

 

import java.util.*;

class Solution {
    static int[][] dist, matrix;
    static boolean[][] visit;
    static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static int N, M;
    
   static void bfs(int x, int y,int n, int m) {

        // (x, y)를 Q에 넣어주고, visit 표시와 dist 값 초기화
        Queue<Integer> Q = new LinkedList<>();
        Q.add(x);
        Q.add(y);
        dist[x][y] = 0;
        visit[x][y] = true;

        // BFS 과정 시작
        while (!Q.isEmpty()) {
            x = Q.poll();
            y = Q.poll();
            for (int k = 0; k < 4; k++) {
                int nx = x + dir[k][0];
                int ny = y + dir[k][1];
                if (nx < 1 || ny < 1 || nx > n || ny > m) continue;  // 지도를 벗어나는 곳으로 가는가?
                if (visit[nx][ny]) continue;  // 이미 방문한 적이 있는 곳인가?
                if (matrix[nx][ny] == 1) continue;  // 갈 수 있는 칸인지 확인해야 한다.

                Q.add(nx);
                Q.add(ny);
                visit[nx][ny] = true;
                dist[nx][ny] = dist[x][y] + 1;
            }
        }

    }
    
    public int solution(int n, int m, int[][] hole) {
        int answer = 0;
        dist = new int[n+1][m+1];
        visit = new boolean[n+1][m+1];
        matrix = new int[n+1][m+1];
        // N = n;
        // M = m;
        
         // dist 배열 초기화
        for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) dist[i][j] = 0;
        // hole 위치 표기
        for(int[] h: hole) {
            matrix[h[0]][h[1]] = 1;
        }
        
        bfs(1,1, n, m);
        
         if(dist[n][m] == 0){
            answer = -1;
        } else {
            answer =  dist[n][m]-1;
        }
        return answer;
    }
}

 

5. 회고

testcase는 통과했지만 전체 테스트는 통과하지 못 했다. 한번 신비로운 신발을 사용하여 점프하는 경우를 아마 통과하지 못 한것 같다. 나의 경우 그냥 정답에서 -1을 해줬는데, 이렇게는 모든 예외케이스를 통과하지 못하는 듯하다. 나중에 한번 더 고쳐보자.