코딩테스트/프로그래머스
PCCP 모의고사 2회 - 보물 지도
feel2
2023. 2. 18. 11:16
반응형
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을 해줬는데, 이렇게는 모든 예외케이스를 통과하지 못하는 듯하다. 나중에 한번 더 고쳐보자.
반응형