ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [프로그래머스]거리두기 확인하기 - JAVA
    문제풀이/프로그래머스 2021. 7. 11. 16:26

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

     

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

    [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1]

    programmers.co.kr

    풀이

    🪑 카카오 인턴십 코딩테스트 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를 반환한다.

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

     

     

    코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    import java.util.*;
     
    class Solution {
        
        int[] dx = {010-1};
        int[] dy = {-1010};
        
        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.lengthcontinue;
                    if(visited[nx][ny] || manhattan > 2continue;
                    
                    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

    댓글

Designed by Tistory.