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

문제

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

프로그래머스

문제 분석

[제한사항]

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

사람, 파티션, 빈 자리에 대한 정보를 담은 배열이 주워졌을 때 해당 맵이 거리두기를 잘 유지하는 지 판별하는 문제이다.

문제의 조건에는 맨해튼 거리가 2 이하로는 앉지 못하고 만약 파티션이 있을 경우에는 이를 허용한다.

문제 접근

문제를 해석해 보면 특정 사람의 위치에서 2번 이동한 거리에 다른 사람이 있으면 거리두기를 유지하지 않는 것이다.

depth 를 2로 제한하고 사람 위치에서 BFS 나 DFS 를 통해 탐색하는데 만약 해당 경로에 사람이 있다면 거리두기를 유지하지 않은 것으로 판단하고 BFS나 DFS 탐색이 끝가지 진행됐다면 해당 위치의 사람은 거리두기를 잘 수행했다고 생각하면된다.

 

여기서 파티션이 있기 때문에 파티션이 있는 경우엔 탐색하지 않는다.

 

아래 코드는 BFS 를 활용하여 풀었다.

코드

import java.util.*;
import java.util.stream.*;
class Solution {
    static int[][] map;
    static List<int[]> people;
    final static int[][] moves = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    public static int[] solution(String[][] places){
        List<Integer> answer = new ArrayList<>();

        for (String[] place : places) {
            initMap(place);
            boolean flag = true;
            for(int[] person : people){
                if (!bfs(person[0], person[1])) {
                    flag = false;
                    break;
                }
            }

            if(flag){
                answer.add(1);
            }else{
                answer.add(0);
            }
        }
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

    public static boolean bfs(int r, int c){
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[map.length][map[0].length];
        queue.offer(new int[]{r, c, 0});
        visited[r][c] = true;
        while(!queue.isEmpty()){
            int[] cur = queue.poll();

            for (int[] move : moves) {
                int nextR = cur[0] + move[0];
                int nextC = cur[1] + move[1];
                int nextDepth = cur[2] + 1;

                if (nextR >= 0 && nextR < map.length && nextC >= 0 && nextC < map[0].length) {
                    if (!visited[nextR][nextC] && map[nextR][nextC] != 2 && nextDepth <= 2) {
                        if (map[nextR][nextC] == 1) {
                            return false;
                        }
                        queue.offer(new int[]{nextR, nextC, nextDepth});
                        visited[nextR][nextC] = true;
                    }
                }
            }
        }
        return true;
    }
    private static void initMap(String[] place) {
        map = new int[5][5];
        people = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                char c = place[i].charAt(j);
                if(c == 'P'){
                    map[i][j] = 1;
                    people.add(new int[]{i, j});
                }else if(c == 'X'){
                    map[i][j] = 2;
                }
            }
        }
    }
}