-
[프로그래머스]거리두기 확인하기 - JAVA문제풀이/프로그래머스 2021. 7. 11. 16:26
[프로그래머스]거리두기 확인하기
풀이
🪑 카카오 인턴십 코딩테스트 2번 문제이다.
문제를 정리해 보자.
- 대기실은 5X5로 5개가 있다.
- 응시자 끼리 맨해튼 거리 2 이하로 앉지 말아야 한다. 단, 파티션으로 자리 사이가 막혀있는 겨우는 앉을 수 있다.
- 맨해튼 거리는 (r1, c1) (r2, c2)일때 |r1 - r2| + |c1 - c2| 이다.
- 각 대기실 별로 모든 응시자가 거리두기를 지키면1, 아니면 0을 담아 반환한다.
🔧 문제 풀이 과정을 생각해 보자.
- 응시자가 앉아있는 위치를 찾는다.
- 응시자의 위치부터 탐색을 한다.
- 빈 책상 으로만 이동한다.
- 맨해튼 거리를 초과하는 위치로는 이동하지 않는다.
- 도중에 다른 응시자를 만나면 안된다. 만났다면 false를 반환한다.
- 탐색 결과에 따라 1 또는 0을 담아준다.
🔹 응시자가 앉아있는 위치를 찾는다.
- 반복문으로 'P'를 찾아준다.
🔹 응시자의 위치부터 탐색을 한다.
- 이때 탐색은 DFS, BFS 어느것을 사용해도 무방하다.
- 나는 BFS를 사용하였는데, 이 문제에서는 맨해튼 거리가 2 이하인 곳으로만 방문하도록 탐색하기 때문에 BFS를 사용하여 가까운 노드부터 순차적으로 탐색을 하도록 구현하였다.
🔹 빈 책상으로만 이동한다.
- 맨해튼 거리 내부에서 빈 책상으로만 이동하면서 다른 응시자를 만날 수 있다면, 거리두기 조건을 만족하지 않은것이 되므로 빈 책상으로만 이동하도록 구현하였다.
- 다른 응시자를 만났다면 맨해튼 거리 내에서 파티션으로 나눠지지 않은 공간에 다른 응시자가 있다는 것을 의미하므로 false를 반환한다.
- 파티션을 만났다면 파티션 방향으로는 더 이상 이동하지 않는다.
코드
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.util.*;class Solution {int[] dx = {0, 1, 0, -1};int[] dy = {-1, 0, 1, 0};public int[] solution(String[][] places) {int[] result = new int[places.length];for(int i = 0; i < places.length; i++){result[i] = isCorrext(places[i]);}return result;}public int isCorrext(String[] board) {for(int i = 0; i < board.length; i++){for(int j = 0; j < board[i].length(); j++){if(board[i].charAt(j) == 'P') {if(!bfs(board, i, j)) return 0;}}}return 1;}public boolean bfs(String[] board, int x, int y) {Queue<Node> q = new LinkedList<>();boolean[][] visited = new boolean[board.length][board.length];q.offer(new Node(x, y));visited[x][y] = true;while(!q.isEmpty()) {Node current = q.poll();for(int i = 0; i < 4; i++) {int nx = current.x + dx[i];int ny = current.y + dy[i];int manhattan = Math.abs(x - nx) + Math.abs(y - ny);if(nx < 0 || ny < 0 || nx >= board.length || ny >= board.length) continue;if(visited[nx][ny] || manhattan > 2) continue;visited[nx][ny] = true;if(board[nx].charAt(ny) == 'X') continue;else if(board[nx].charAt(ny) == 'P') return false;else q.offer(new Node(nx, ny));}}return true;}public class Node {int x;int y;public Node(int x, int y) {this.x = x;this.y = y;}}}cs '문제풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스]셔틀버스 - JAVA (0) 2021.09.04 [프로그래머스]무지의 먹방 라이브 - JAVA (0) 2021.09.03 [프로그래머스]표 편집 - JAVA (1) 2021.07.10 [프로그래머스]로또의 최고 순위와 최저 순위 - JAVA (0) 2021.07.04 [프로그래머스]모두 0으로 만들기 - JAVA (0) 2021.06.08