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

https://school.programmers.co.kr/learn/courses/30/lessons/81302
프로그래머스 - 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기 LV2

input - 5 by 5 행렬
거리두기 성립 조건 - 맨해튼 거리가 2 이상 or 파티션으로 막힌 경우
맨해튼 거리 = 가로, 세로 길이의 차의 절댓값의 합
파티션으로 막히지 않은 경우 - > 맨해튼 거리가 2 이하이면서 사이를 막는 파티션이 없음

P - 응시자 자리
O - 빈 테이블
X - 파티션

Solution

모든 좌표들을 돌면서, 응시자가 위치한 경우 반경 2의 자리들을 탐색

		*
	*   *   *   
*   *   P   *   *
    *   *   *
        *

• 중에 파티션이 없으면서 연결된 부분들을 탐색

BFS를 이용하여 탐색하면서, 맨해튼 거리가 2 이하인 좌석 중 도달할 수 있는 응시자가 있는지를 확인하면 됨.

import java.util.*;

class Solution {
    
    public static int[] dx = new int[]{-1,0,1,0};
    public static int[] dy = new int[]{0,1,0,-1};
    public int[] solution(String[][] places) throws Exception {

        int[] answer = new int[5];
        
        // foreach 문에서 사용할 반복자
        int c=0;
        for(String[] place : places){
            System.out.println("-----------"+(c+1)+" 번째 대기실-----------");
            
            int ans=1;
            for(int i=0;i<5;i++){
                for(int j=0;j<5;j++){
                    if(place[i].charAt(j)=='P'){
                        boolean[][] visited = new boolean[5][5];
                        
                        // 해당 응시자의 좌표를 기준으로 진행한 탐색에서 거리두기를 유지하지 않은 응시자가 있으면
                        ans= calc(place,i,j,visited);
                        
                        // ans가 0이 나온 순간 다른 응시자들의 거리두기는 확인할 필요가 없어짐
                        if(ans==0){
                            break;
                        }
                    }
                }
                if(ans==0){
                    break;
                }
            }
            answer[c]=ans;
            c++;
        }
        
        return answer;
    }
    
    // 응시자가 앉아있는 좌표 X, Y 를 받아서 BFS를 시작하는 메소드
    public static int calc(String[] place,int x, int y, boolean[][] visited){
        System.out.println("응시자의 위치 : ("+x+", "+y+") 부터 탐색");
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x,y});
        visited[x][y]=true;
        while(!queue.isEmpty()){
            int[] data = queue.poll();
            for(int m=0;m<4;m++){
                int newX=data[0]+dx[m];
                int newY=data[1]+dy[m];
                
                // 새로 이동하려는 좌표가 유효성 탐색.
                // 1. 인덱스가 0에서 4 사이인지 확인
                // 2. 맨해튼 거리가 3인 좌표는 탐색할 필요가 없음
                if(newX<0 || newX>=5 || newY<0 || newY>=5 || distance(x,y,newX,newY)>2){
                    continue;
                }
                
                // 이동하려는 좌표가 다른 응시자 이면 거리두기 X
                if(place[newX].charAt(newY)=='P'&& !visited[newX][newY]){
                    System.out.println("("+x+", "+y+")가 ("+newX+", "+newY+")랑 거리두기가 안됨. 둘 사이의 거리: "+distance(x,y,newX,newY));
                    return 0;
                }

                // 이동하려는 좌표가 빈 테이블 이고 방문하지 않은 좌석 일때 해당 위치를 새로 방문
                if(place[newX].charAt(newY)=='O' && !visited[newX][newY]){
                    visited[newX][newY]=true;
                    queue.add(new int[]{newX,newY});
                    System.out.println("새로 방문할 좌표: ("+newX+", "+newY+")");
                }
                
            }
        }
          
        return 1;
    }
 
    // 맨하탄 거리를 계산하는 메소드
    public static int distance(int firstX, int firstY, int secondX, int secondY){
        return Math.abs(firstX-secondX)+Math.abs(firstY-secondY);
    }
}