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

 

 

응시자들이 대기실에서 거리두기를 지키고 있는지 확인하는 문제. char[][] 2차원 배열과 방향 배열(dx/dy)을 다루는 대표적인 격자 탐색 문제였다. 레벨 2라서 그런지 확실히 어려웠다... 카카오 문제라는데 이걸 어떻게 가서 푸는거지 ㅋ큐
 
 

1. 문제 설명

5개의 대기실이 주어진다. 각 대기실은 5×5 격자이고, 각 칸은 다음 셋 중 하나다.

• P : 응시자
• O : 빈 테이블
• X : 파티션

거리두기 규칙은 이렇다.

• 두 응시자 사이의 맨해튼 거리가 2 이하면 거리두기를 지키지 않은 것이다.
• 단, 두 응시자 사이를 파티션(X)이 막고 있으면 지킨 것으로 본다.

맨해튼 거리 = |행 차이| + |열 차이|. 즉 상하좌우로 몇 칸 떨어졌는지.

 
 
대기실별로 모든 응시자가 거리두기를 지키면 1, 한 명이라도 어기면 0을 담아 길이 5짜리 배열로 반환한다.
 
입력 형태는 다음과 같다. 

places = String[][]   // 대기실 5개
places[i] = String[]  // i번째 대기실 (문자열 5줄)
places[i][j] = String // i번째 대기실의 j번째 줄, 예: "POOOP"

 

2. 풀이 방법

 
 
거리두기 위반은 두 경우뿐이다.

1. 맨해튼 거리 1 (바로 상하좌우 옆칸)에 다른 P가 있다 → 무조건 위반.
2. 맨해튼 거리 2인데, 그 사이에 파티션이 없다 → 위반.

거리 2는 직선으로 두 칸(P _ P) 또는 대각선(ㄱ자) 두 가지인데, 둘 다 가운데를 빈 테이블(O)이 이어주는 경우에만 위반이다. 그래서 이렇게 탐색한다.

각 P에서 상하좌우로 한 칸 본다.

• 옆칸이 P → 거리 1 위반
• 옆칸이 O → 그 O에서 한 칸 더 나가서 P가 있는지 확인 (거리 2 위반)
• 옆칸이 X → 막혀 있으니 그 방향은 무시

이 방식이면 파티션이 알아서 "벽" 역할을 한다. X를 만나면 더 안 나가니까, 파티션이 막은 경로는 자연스럽게 걸러진다.

 

3. 헷갈렸던 포인트 정리 

 
 
처음에 room 안에 대기실 여러 개가 들어있는 줄 알았는데 아니었다. 

• places = 대기실 5개 전체를 담은 큰 상자
• room (char[][]) = 대기실 딱 1개를 표현하는 5×5 격자

• places[i]는 String[]이라, 특정 칸을 보려면 places[i][2].charAt(3)처럼 매번 .charAt()을 써야 한다.
• room은 char[][]라, room[2][3]처럼 [행][열] 좌표로 바로 접근한다. 격자 탐색(상하좌우 이동)엔 이게 훨씬 편하다.

반복문에서는 대기실 하나를 만들어 검사하고, 다음 i로 넘어가면 새 room을 다시 만드는 식으로 한 개씩 처리한다.

 

이때 char[][]는 사실 1차원 배열들을 묶어놓은 배열이다. 그래서 대괄호 개수에 따라 의미가 달라진다.

char[][] room = new char[5][5];

room        // 대괄호 0개 → 대기실 전체 (char[][])
room[j]     // 대괄호 1개 → j번째 "줄 하나" 전체 (char[])
room[j][k]  // 대괄호 2개 → j행 k열의 글자 하나 (char)  예: 'P'

 
서류함으로 비유하면, room은 서랍 5개짜리 서류함, room[j]는 서랍 한 칸 통째로, room[j][k]는 그 서랍 안의 종이 한 장이다.
그리고 String.toCharArray()는 문자열을 1차원 char 배열로 만들어준다.
 

"POOOP".toCharArray();  // ['P','O','O','O','P']  ← char[] (1차원)

 
 
그래서 아래 대입이 성립한다. 좌변 room[j]도 char[], 우변도 char[]라 타입이 같아서 한 줄 통째로 쏙 들어간다.

room[j] = place[j].toCharArray();  // j번째 줄을 통째로 넣기

 

 

 
3 - d는 왜 exclude(제외) 값이다. 거리 2를 검사할 때, O에서 한 칸 더 나가 P를 찾는데 방금 온 방향으로 되돌아보면 안 된다.
예를 들어 P(0,0)에서 오른쪽으로 가서 O(0,1)에 도착했다고 하자. 여기서 사방을 둘러볼 때, 왼쪽을 보면 방금 출발한 그 P(0,0)가 보인다.  이걸 주변에 P가 있다고 생각하고 위반으로 착각하면 안 되니까, 왔던 방향은 검사에서 꼭 빼줘야한다. 
 
 
이때 방향 배열을 반대 방향이 3 - d로 계산되도록 배치하는 게 핵심이다. 상좌하우로 dx,dy를 설정해주면 각각 반대방향의 인덱스를 서로 합했을 때 3이 된다. 이 원리를 이용하면 3-d일때 반대방향이 나오게 된다. 
 
 

int[] dx = {-1, 0, 0, 1};
int[] dy = { 0,-1, 1, 0};  // 0:위, 1:왼, 2:오, 3:아래

 
 
이 순서면 3 - d가 항상 정확히 반대 방향의 인덱스가 된다. 그래서 isNextToVolunteer(room, nx, ny, 3 - d)는 방금 걸어온 방향만 빼고 주변에 응시자가 있는지 확인하는 함수이다. 
 

4. 전체 코드

class Solution {
   
    private static final int dx[] = {0,-1,1,0};
    private static final int dy[] = {-1,0,0,1}; //상좌우하 방향 
    
    //방향 인덱스 상-0, 하-3, 좌-1, 우-2 => 반대 방향끼리 인덱스 더하면 3 
    
    
    private boolean isNextToVolunteer(char[][] room, int x, int y, int exclude){
        //원래 검사를 시작했던 응시자는 제외 exclude 
        
        for(int d = 0; d < 4; d++){
            if(d==exclude)continue; 
            
            int nx = x + dx[d];
            int ny = y + dy[d]; 
            
            if(ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length)continue; 
            if(room[ny][nx] == 'P')return true; 
            
        }
        
        return false; 
        
    }//빈 테이블과 인접한 위치 중 응시자가 있다면 거리두기가 지켜지지 않은 것 
    
    
    
    private boolean isDistanced(char[][] room){
        
        for(int y = 0; y<room.length;y++){
            for(int x = 0; x<room[y].length;x++){
                if(room[y][x]!='P')continue; // 응시자가 아니면 건너뛰기 
                //거리두기 검사 
                if(!isDistanced(room,x,y))return false; 
            }       
        }        
        return true; 
    }//해당 대기실이 거리두기를 지키고 있는지 검사 
    
    
    private boolean isDistanced(char[][] room, int x, int y){
        
        for(int d = 0; d<4; d++){
            int nx = x + dx[d];
            int ny = y + dy[d]; 
            
            if(ny < 0||ny >= room.length|| nx < 0 || nx >= room[ny].length)continue; 
            
            switch(room[ny][nx]){ 
                    case 'P': return false;
                    case 'O' :
                    if(isNextToVolunteer(room,nx,ny,3-d))return false;  //3-d는 반대방향 
                    break;  
                    //인접한 곳에 다른 응시자가 있는지 검사 
                    //빈 테이블과 인접한 위치 중 응시자가 있다면 거리두기를 지키지 않은 것        
            }              
        }
        return true; 
    }//해당 대기실에서 x,y 위치의 응시자가 거리두기를 지키고 있는지 검사 
    
    
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        
        for(int i = 0; i < answer.length; i++){
            String[] place = places[i]; 
            char[][] room = new char[place.length][];//히나의 대기실 
            for(int j = 0; j < room.length; j++){
                room[j] = place[j].toCharArray(); // PXPXP => P,X,P,X,P로 분할하여 받기 
            }
            //거리두기 검사 후 answer에 기록
            if(isDistanced(room)){
                answer[i] = 1;
            }else{
                answer[i] = 0;
            }
            
        }
        return answer;
         
        
    }
}

 
 
 
 
 

정리

• char[][] room 한 개가 대기실 한 개다. places[i](String[])를 좌표 접근이 쉬운 char[][]로 바꾼 것이다. 
• char[][]는 배열의 배열이라 room[j]는 줄 하나(char[]), room[j][k]가 글자 하나. 그래서 room[j] = place[j].toCharArray()로 한 줄을 통째로 넣는다.
• 방향 배열을 위·왼·오·아래 순으로 두면 반대 방향이 3 - d가 되고, 이걸 exclude로 넘겨 왔던 길을 되돌아보지 않게 한다.
• 파티션(X)은 만나면 더 안 나가므로 자연스럽게 "벽" 역할을 해서, 거리 2 검사를 간단하게 만들어준다