<프로그래머스> 거리두기 확인하기

<링크>

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

프로그래머스

 

 

 

 

 

<문제>

• 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
• 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
  • 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
  • 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
  • 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
• 예를 들어,

• 5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

<제한사항>

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

 

<입력 및 출력>

 

<아이디어>

1. bfs 만 돌리면 되겠는데..?
2. 대신 특정 조건에 맞춰서 1,0 값을 넣어주자.
3. X일때랑 O일때, 판단하는 조건을 잘 넣어 주기!!

 

<풀이 - Java >

import java.util.*;
class Solution {
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    public int[] solution(String[][] places) {
        int[] answer = new int [places.length];
        for (int i = 0 ;i<places.length; i++){
            String[] localHuman = places[i];
            // System.out.print(Arrays.toString(localHuman));
            boolean trueFalse = true;
            for (int r = 0; r<5 && trueFalse; r++){
                for (int c = 0 ; c<5 && trueFalse ; c++){
                    if (localHuman[r].charAt(c) =='P'){
                        if(!bfs(r,c,localHuman)){
                            trueFalse = false;
                        }
                    }
                }
            }
            if (trueFalse == true){
                answer[i] = 1;
            }else{
                answer[i] = 0;
            }

        }
        return answer;
    }
    
    public static boolean bfs(int x, int y, String[] human) {
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[5][5];
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            // 뽑아내고
            int[] position = queue.poll();
            // 움직인 위치
            int ex = position[0];
            int ey = position[1];
            // 최대 거리가 2이상이라며... 맨허튼 length
            int len = Math.abs(ex - x) + Math.abs(ey - y);

            // len이 0이상, 2이하! 그리고 사람의 현재 위치가 P이면...
            if (len > 0 && human[ex].charAt(ey) == 'P' && len <= 2) {
                return false;
            }

            if (len < 2) {
                for (int i = 0; i < 4; i++) {
                    int nx = ex + dx[i];
                    int ny = ey + dy[i];

                    // 갈수 있고!, 방문 안했고!, X가 아니면!
                    if (isValue(nx, ny) && !visited[nx][ny] && human[nx].charAt(ny) != 'X') {
                        // queue에 너어주세요
                        queue.add(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return true;
    }
    
    public static boolean isValue(int i, int j){
        return i>=0 && i <5 && j>=0 && j<5;
    }
}