문제풀이 접근
1. 한번에 5개의 케이스가 주어지므로, places[]로 처음에 순회를 해야한다.
2. 배열에서 'P'를 찾으면, 해당 좌표를 bfs 돌려준다.
2-1. 해당 좌표를 큐에 넣고, 방문 처리 해준다.
2-2. 범위를 초과했거나, 방문한 지역이면 continue 해준다.
2-3. 만약에 순회한 지역에서 'P'를 찾고, 거리가 2 이내라면 false를 리턴한다.
2-4. 'O'이면서 거리가 2 이내일 때, 큐에 넣어서 탐색을 계속 이어나간다.
3. bfs의 결과를 flag에 반영하고, 그 결과에 따라서 answer 배열 값을 업데이트 해준다.
import java.util.*;
class Solution {
static int [] dx = {1,0,-1,0};
static int [] dy = {0,1,0,-1};
static boolean [][] visited;
static Queue<int []> queue;
public int[] solution(String[][] places) {
int[] answer = new int[5];
int idx = 0;
for(String [] place : places) {
visited = new boolean[5][5];
queue = new LinkedList<>();
boolean flag = true;
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++) {
if (place[i].charAt(j) == 'P') {
if (!bfs(place,i,j)) {
flag = false;
break;
}
}
}
}
if (flag) answer[idx++] = 1;
else answer[idx++] = 0;
}
return answer;
}
public boolean bfs(String [] place, int i, int j) {
visited[i][j] = true;
queue.add(new int[]{i,j});
while(!queue.isEmpty()) {
int [] cur = queue.poll();
int x = cur[0];
int y = cur[1];
for(int dir = 0; dir < 4; dir++){
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
if (visited[nx][ny]) continue;
int dist = Math.abs(nx - i) + Math.abs(ny - j);
// 가르키는 곳이 P이고 거리가 2이하면 false 리턴
if (place[nx].charAt(ny) == 'P' && dist <= 2) {
return false;
}
// 빈 자리이고, 거리가 2 이내일 때 다시 큐에 넣어서 돌린다.
else if (place[nx].charAt(ny) == 'O' && dist <= 2) {
queue.add(new int[]{nx,ny});
visited[nx][ny] = true;
}
}
}
return true;
}
}
문제풀이 회고
차근차근 생각한다면 딱히 어렵지 않았는데, 너무 많이 생각하느라 답을 참고했다.
까다로웠던 부분은, 빈자리 일 때, 큐에 넣어서 다시 탐색을 반복하는 건 알겠는데 거리가 2 이내 이부분이 많이 헷갈렸다.
위 예제를 참고할 때, (1,2) 지점에서 BFS를 돌린다고 가정하자.
일단 거리가 1인 지점에는 P가 없으니 계속 진행할 것이고 (0,2) 지점이 'O'이고, 거리도 2 이내니 큐에 넣어서 탐색을 다시 이어나가야 한다.
이제 (0,2)에서 탐색을 진행할때, (0,3)에서 거리가 2인 P가 있으므로 false를 리턴해야 한다.
주의점
- 해당 거리의 차이는 무조건 P에서 계산한다. (O에서 BFS를 돌렸더라도 거리 기준은 처음에 P가 된다.)
- 그래서 (1,2)와 (0,3)을 비교할 때, 거리가 2이므로 false를 리턴해준다!
이렇게 풀어서 쓰니 좀 이해가 되는데?
'Algorithm > 프로그래머스 코딩테스트 문제풀이전략' 카테고리의 다른 글
[프로그래머스] Lv.1 시저 암호 (0) | 2024.04.16 |
---|---|
[프로그래머스] Lv.1 자연수 뒤집어 배열로 만들기 (0) | 2024.04.16 |
[프로그래머스] Lv.2 행렬의 곱셈 (0) | 2024.04.16 |
[프로그래머스] Lv.2 삼각 달팽이 (0) | 2024.04.16 |
[프로그래머스] Lv.2 교점에 별 만들기 (0) | 2024.04.15 |