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

문제 링크

BFS를 통한 탐색을 통해 문제를 풀었다.

---

전체 코드는 다음과 같다

import java.util.*;

class Solution {
    
    int[] dx = {0, -1, 0, 1};
    int[] dy = {-1, 0, 1, 0};
    
    boolean[][] visited;
    String[][] room;
    
    public int[] solution(String[][] places) {
        
        int[] answer = new int[5];
        
        for(int i = 0; i < places.length; i++){
            
            answer[i] = 1;
            
            visited = new boolean[5][5];
            room = new String[5][5];
            
            String[] now = places[i];
            
            for(int j = 0; j < 5; j++){
                
                String row = now[j];
                
                for(int k = 0; k < 5; k++){
                    room[j][k] = row.substring(k, k+1);
                }
            }
            
            for(int j = 0; j < 5; j++){
                if(answer[i] == 0)
                    break;
                for(int k = 0; k < 5; k++){
                    if(room[j][k].equals("P")){
                        int[] start = {j, k};
                        answer[i] = bfs(start);
                        visited = new boolean[5][5];
                    }
                    
                    if(answer[i] == 0)
                        break;
                }
            }
        }
        
        return answer;
    }
    
    public int bfs(int[] start){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        visited[start[0]][start[1]] = true;
        
        while(!queue.isEmpty()){
            
            int[] now = queue.poll();
            
            for(int i = 0; i < 4; i++){
                int[] next = {now[0] + dy[i], now[1] + dx[i]};
                int len = Math.abs(start[0] - next[0]) + Math.abs(start[1] - next[1]);
                
                if(next[0] < 0 || next[1] < 0 || next[0] > 4 || next[1] > 4)
                    continue;
                
                if(visited[next[0]][next[1]])
                    continue;
                
                if(len > 2)
                    continue;
                
                if(room[next[0]][next[1]].equals("X"))
                    continue;
                
                if(room[next[0]][next[1]].equals("P"))
                    return 0;
                
                queue.add(next);
                visited[next[0]][next[1]] = true;
            
            }
        }
        
        return 1;
    }
}

---

탐색을 위한 배열 dx, dy
방문 여부를 저장하는 visited
대기실의 정보를 저장하는 room을 전역변수로 선언했다.

class Solution {
    
    int[] dx = {0, -1, 0, 1};
    int[] dy = {-1, 0, 1, 0};
    
    boolean[][] visited;
    String[][] room;

대기실의 갯수가 5개이므로
정답을 저장하는 배열 answer의 크기를 5로 초기화하였다.

    public int[] solution(String[][] places) {
        
        int[] answer = new int[5];

대기실의 개수만큼 반복문을 통해 반복하며
해당 대기실의 정답을 1로 초기화하고
visited와 room 배열을 초기화하고
room 배열에 해당 대기실의 정보를 담는다.

        for(int i = 0; i < places.length; i++){
            
            answer[i] = 1;
            
            visited = new boolean[5][5];
            room = new String[5][5];
            
            String[] now = places[i];
            
            for(int j = 0; j < 5; j++){
                
                String row = now[j];
                
                for(int k = 0; k < 5; k++){
                    room[j][k] = row.substring(k, k+1);
                }
            }
            
            ...
        }

그 다음으로 대기실에 사람들이 거리를 두고 앉았는지 확인한다.

room 배열을 탐색하며 사람이 앉은 곳을 찾으면 그 곳을 기준으로 bfs() 함수를 실행해 탐색을 진행한다.
bfs()함수의 매개변수로 탐색의 시작 점을 넘겨준다.
탐색이 끝나면 visited 배열을 다시 초기화한다.

bfs()함수는 사람이 거리를 두고 앉았으면 1을, 아니면 0을 반환한다.
이를 해당 대기실의 정답 배열에 저장한다.

정답 배열에 0이 저장되었으면 그 대기실은 더이상 탐색할 필요가 없으므로 반복문을 빠져나와 다음 대기실로 넘어간다.

        for(int i = 0; i < places.length; i++){
            
            ...
            
            for(int j = 0; j < 5; j++){
                if(answer[i] == 0)
                    break;
                for(int k = 0; k < 5; k++){
                    if(room[j][k].equals("P")){
                        int[] start = {j, k};
                        answer[i] = bfs(start);
                        visited = new boolean[5][5];
                    }
                    
                    if(answer[i] == 0)
                        break;
                }
            }
        }
                
        return answer;
    }

bfs() 함수는 다음과 같다.

매개변수로 받은 시작점을 queue에 넣은 후 visited에 시작점을 방문한것으로 표시한다.

BFS 탐색을 이용해 큐가 빌 때까지 다음 내용을 반복한다.

큐에서 데이터를 꺼낸 후, 해당 지점의 상하좌우를 탐색한다.

탐색 지점이 대기실을 벗어나지 않고,
시작 지점과의 맨해튼 거리가 2이하이고,
파티션으로 막힌 지점이 아니라면
이하의 내용을 확인한다.

만약 그 지점에 사람이 있다면
시작 지점(사람이 앉아 있는 곳)과 맨해튼 거리가 2이하인데 파티션으로 막혀 있지 않은곳에 사람이 있는 것이므로 규칙을 위반한것이다.
0을 반환하고 함수를 멈춘다.

사람이 아닌 테이블 공간이라면
queue에 이 지점을 넣은 후
visited에 방문했음을 표시한다.

만약 이대로 큐가 빈다면 규칙을 위반한 경우가 없는 것이므로 1을 반환하고 함수를 종료한다.

    public int bfs(int[] start){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        visited[start[0]][start[1]] = true;
        
        while(!queue.isEmpty()){
            
            int[] now = queue.poll();
            
            for(int i = 0; i < 4; i++){
                int[] next = {now[0] + dy[i], now[1] + dx[i]};
                int len = Math.abs(start[0] - next[0]) + Math.abs(start[1] - next[1]);
                
                if(next[0] < 0 || next[1] < 0 || next[0] > 4 || next[1] > 4)
                    continue;
                
                if(visited[next[0]][next[1]])
                    continue;
                
                if(len > 2)
                    continue;
                
                if(room[next[0]][next[1]].equals("X"))
                    continue;
                
                if(room[next[0]][next[1]].equals("P"))
                    return 0;
                
                queue.add(next);
                visited[next[0]][next[1]] = true;
            
            }
        }
        
        return 1;
    }