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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/81302#fn1

프로그래머스

 

---

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 갔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 대기실에서 거리를 두고 앉아야 합니다. 대기실은 5개이며, 각 대기실은 5x5 크기로 구성되어 있습니다. 응시자들 간의 맨해튼 거리가 2 이하로 앉지 않도록 해야 하며, 파티션(X)으로 막혀 있는 경우에는 거리두기를 지킨 것으로 간주합니다.

대기실의 구조는 다음과 같은 기호로 표현됩니다:

• P: 응시자가 앉아있는 자리
• O: 빈 테이블
• X: 파티션

주어진 대기실 구조를 바탕으로, 각 대기실에서 응시자들이 거리두기를 잘 지키고 있는지 확인하고, 결과를 배열로 반환해야 합니다. 모든 응시자가 거리두기를 지키고 있으면 1, 한 명이라도 지키지 않으면 0을 반환합니다.

접근 방법

이 문제를 해결하기 위해 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색) 알고리즘을 사용할 수 있습니다. 각 대기실의 구조를 탐색하면서 응시자(P) 간의 거리를 체크하고, 거리두기 규칙을 위반하는 경우를 찾아내는 방식입니다.

1. 대기실 구조 파악: 각 대기실을 2차원 배열로 표현하고, 응시자(P)의 위치를 찾습니다.
2. 거리 체크: 각 응시자에 대해 BFS 또는 DFS를 통해 주변의 응시자와의 거리를 체크합니다.
   • 맨해튼 거리 계산: 두 응시자 간의 맨해튼 거리를 계산하여 2 이하인 경우를 확인합니다.
   • 파티션(X) 체크: 파티션이 있는 경우에는 거리두기를 지킨 것으로 간주합니다.
3. 결과 저장: 모든 응시자가 거리두기를 지키고 있는지 확인한 후, 결과를 배열에 저장합니다.

 

bfs방법

import java.util.*;

class Solution {
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};

    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        
        for(int i = 0; i < places.length; i++) {
            if (!checkMap(places[i])) {
                answer[i] = 0;
            } else {
                answer[i] = 1;
            }
        }
        
        return answer;
    }
    
    public boolean checkMap(String[] arr) {
        String[][] map = new String[arr.length][arr[0].length()];
        for(int i = 0; i < map.length; i++) {
            map[i] = arr[i].split("");
        }
        
        for(int i = 0; i < map.length; i++) {
            for(int j = 0; j < map[i].length; j++) {
                if (map[i][j].equals("P")) {
                    if (!bfs(new Node(i, j, 0), map)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    
    public boolean bfs(Node node, String[][] map) {
        Queue<Node> q = new LinkedList<>();
        boolean[][] v = new boolean[map.length][map[0].length];
        v[node.r][node.c] = true;
        q.add(node);
        
        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.cnt > 2) continue;
            if (cur.cnt > 0 && cur.cnt <= 2 && map[cur.r][cur.c].equals("P")) return false;
            
            for (int i = 0; i < 4; i++) {
                int nr = dr[i] + cur.r;
                int nc = dc[i] + cur.c;
                
                if (nr < 0 || nc < 0 || nr >= map.length || nc >= map[0].length || v[nr][nc] || map[nr][nc].equals("X")) continue;
                v[nr][nc] = true;
                q.add(new Node(nr, nc, cur.cnt + 1));
            }
        }
        return true;
    }
    
    static class Node {
        int r, c, cnt;
        public Node(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
}

 

 

dfs방법

import java.util.Arrays;

class Solution {
    static String[][] map;
    static boolean[][] v;
    static boolean flag;
    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, -1, 0, 1};

    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        for (int i = 0; i < 5; i++) {
            flag = false;
            map = new String[5][5];
            for (int j = 0; j < map[i].length; j++) {
                map[j] = places[i][j].split("");
            }

            loop:
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    if (map[j][k].equals("P")) {
                        v = new boolean[5][5];
                        dfs(0, j, k);
                        if (flag) {
                            break loop;
                        }
                    }
                }
            }
            answer[i] = flag ? 0 : 1;
        }
        return answer;
    }
    
    public static void dfs(int depth, int r, int c) {
        if (depth >= 2) {
            return;
        }
        v[r][c] = true;
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5 || v[nr][nc]) continue;

            if (map[nr][nc].equals("O")) dfs(depth + 1, nr, nc);
            else if (map[nr][nc].equals("P")) {
                flag = true;
                return;
            } else if (map[nr][nc].equals("X")) {
                continue;
            }
        }
    }
}