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

문제

접근방법

1. 제한사항이 결국 5 * 5 대기실이 5개가 있기때문에 브루트포스로 접근하여 문제를 해결하기로 했다.

2. 기본적으로 참가자들을 모두 담을 자료구조가 필요했기때문에 간단히 큐를 생각해서 참가자들의 자리를 배열로 넣었다.

3. 큐에서 꺼낸 참가자의 4방을 모두 탐색한다.

3-1. 파티션인 경우 해당사항이 없으니 넘어간다.

3-2. 다른 참가자인 경우 False

3-3. 빈자리인 경우 한 번더 4방 탐색을 진행한다. 이 때 기존에 시작했던 참가자의 자리는 탐색하면 안되기에 체크해준다.

3-4. 4방 탐색시 다른 참가자인 경우 False

 

코드

import java.util.*;

class Solution {
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        int num = 0;
        for(String[] place : places){
            String map[][] = new String[5][5];
            Queue<int[]> q = new LinkedList<>();
            for(int i=0;i<5;i++){
                String str[] = place[i].split("");
                for(int j=0;j<5;j++){
                    map[i][j] = str[j];
                    if(str[j].equals("P")){
                        q.add(new int[]{i,j});
                    }
                }
            }
            
            boolean t = true;            
            while(!q.isEmpty()){
                int arr[] = q.poll();
                int xPos = arr[0];
                int yPos = arr[1];
                // 1차 사방탐색(맨해튼 거리 = 1)
                for(int i=0;i<4;i++){
                    int nx = xPos + dx[i];
                    int ny = yPos + dy[i];                    
                    // 범위를 초과한 경우 해당되지 않음
                    if(nx < 0 || ny <0 || nx >4 || ny> 4) continue;
                    // 파티션인 경우 해당되지 않음
                    if(map[nx][ny].equals("X")) continue;
                    // 사람인 경우 끝
                    else if(map[nx][ny].equals("P")) {
                        t = false;
                        break;
                    }
                    // 빈자리인 경우 그 전 자리의 사람을 빼고 탐색해야함
                    else if(map[nx][ny].equals("O")){
                        for(int j=0;j<4;j++){
                            int nnx = nx + dx[j];
                            int nny = ny + dy[j];
                            // 범위를 초과한 경우 해당되지 않음
                            if(nnx < 0 || nny <0 || nnx >4 || nny> 4) continue;
                            // 기존 탐색 시작했던 자리는 빼고 탐색
                            if(nnx == xPos && nny ==yPos) continue;
                            else if(map[nnx][nny].equals("P")){
                                t = false;
                                break;
                            }
                        }
                    }
                }                
            }
            if(t){
                answer[num] = 1;
            }
            num+=1;
        }
        return answer;
    }
}