[프로그래머스]거리두기 확인하기 - JAVA

[프로그래머스]거리두기 확인하기

코딩테스트 연습 - 거리두기 확인하기

풀이

🪑 카카오 인턴십 코딩테스트 2번 문제이다.

 

문제를 정리해 보자.

• 대기실은 5X5로 5개가 있다.
• 응시자 끼리 맨해튼 거리 2 이하로 앉지 말아야 한다. 단, 파티션으로 자리 사이가 막혀있는 겨우는 앉을 수 있다.
• 맨해튼 거리는 (r1, c1) (r2, c2)일때 |r1 - r2| + |c1 - c2| 이다.
• 각 대기실 별로 모든 응시자가 거리두기를 지키면1, 아니면 0을 담아 반환한다.

 

🔧 문제 풀이 과정을 생각해 보자.

1. 응시자가 앉아있는 위치를 찾는다.
2. 응시자의 위치부터 탐색을 한다.
3. 빈 책상 으로만 이동한다.
   • 맨해튼 거리를 초과하는 위치로는 이동하지 않는다.
   • 도중에 다른 응시자를 만나면 안된다. 만났다면 false를 반환한다.
4. 탐색 결과에 따라 1 또는 0을 담아준다.

 

🔹 응시자가 앉아있는 위치를 찾는다.

- 반복문으로 'P'를 찾아준다.

 

🔹 응시자의 위치부터 탐색을 한다.

- 이때 탐색은 DFS, BFS 어느것을 사용해도 무방하다.

- 나는 BFS를 사용하였는데, 이 문제에서는 맨해튼 거리가 2 이하인 곳으로만 방문하도록 탐색하기 때문에 BFS를 사용하여 가까운 노드부터 순차적으로 탐색을 하도록 구현하였다.

 

🔹 빈 책상으로만 이동한다.

- 맨해튼 거리 내부에서 빈 책상으로만 이동하면서 다른 응시자를 만날 수 있다면, 거리두기 조건을 만족하지 않은것이 되므로 빈 책상으로만 이동하도록 구현하였다.

- 다른 응시자를 만났다면 맨해튼 거리 내에서 파티션으로 나눠지지 않은 공간에 다른 응시자가 있다는 것을 의미하므로 false를 반환한다.

- 파티션을 만났다면 파티션 방향으로는 더 이상 이동하지 않는다.

 

 

코드

import 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;
        }
    }
}