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

해당 문제 링크

거리두기 확인하자 - 프로그래머스 LV2

문제해설

대기실은 5개, 각 대기실의 크기는 5x5이고 면접자간 간격이 맨해튼거리 2이하로 앉지 않은 강의실을 체크한다.

테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다.

문제풀이

강의실 크기 5x5, 강의실 갯수 5의 제한조건을 보고 시간복잡도의 고민은 하지않았고 알고리즘은 BFS탐색 방식을 썻다.

사람이 앉은자리(P) 에서 상하좌우 4방향 탐색을 한 칸씩 진행하되 최대 2칸까지만 탐색한다.

1. 사람이 앉은자리(P)를 만나면 바로 0값 리턴
2. 빈 자리(O)를 만나면 다시 상하좌우 탐색
3. 파티션(X)를 만나면 탐색 안함

으로 BFS탐색 로직을 작성하면 된다.

소스코드

import java.util.*;

class Solution {
    final char people = 'P';
    final char empty = 'O';
    
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        
        // 강의실
        for(int i=0; i<places.length; i++){
            answer[i] = checkPlace(places[i]);
        }
        return answer;
    }
    
    public int checkPlace(String[] place){
        
        for(int i=0; i<place.length; i++){
            for(int j=0; j<place[i].length(); j++){
            	// 강의실 자리
                char space = place[i].charAt(j);
                // 사람이 앉은 자리만 탐색
                if(space == people){
                	//해당 자리가 맨해튼거리 2이하를 준수했는가
                    boolean isManhattanDistance = checkManhattanDistance(place, i, j);
                    //준수안했다면 0리턴
                    if(!isManhattanDistance){
                        return 0;
                    }
                }
            }
        }
        
        return 1;
    }
    
    public boolean checkManhattanDistance(String[] place, int row, int column){
    	// 방문여부 확인
        boolean[][] visited = new boolean[5][5];
        
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(row, column, 0));
        visited[row][column] = true;
        
        //상하좌우
        int[] dx = {0, 1, 0, -1};
        int[] dy = {-1, 0, 1, 0};
        int LimmitMangattanDistance = 2;
        char empty = 'O';
        
        while(!queue.isEmpty()){
            Location location = queue.poll();
            if(location.depth >= LimmitMangattanDistance){
                return true;
            }
            
            for(int i=0; i<4; i++){
                int mx = location.col + dx[i];
                int my = location.row + dy[i];
                // 배열 경계값 확인
                if(mx >= 0 && my >= 0 && mx < 5 && my < 5){
                	//방문 여부
                    if(!visited[my][mx]){
                    	//다음 탐색위치
                        char space = place[my].charAt(mx);
                        //사람이 앉은자리이면 false
                        if(space == people){
                            return false;
                        }
                        //빈자리이면 다시 재탐색
                        if(space == empty){
                            queue.add(new Location(my, mx, location.depth + 1));    
                        }
                    }
                }
            }
        }
        
        //2칸 이내에 파티션으로 다 막혀있는 경우
        return true;
    }
    class Location{
        int row;
        int col;
        int depth;
        
        Location(int row, int col, int depth){
            this.row = row;
            this.col = col;
            this.depth = depth;
        }
    }
}

---

다른사람풀이

탐색을 DFS로 해도 문제없다.