알고리즘 풀이 - 프로그래머스(거리두기 확인하기(Lv 2), BFS)

 

관련글

 

그래프 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

 

코로나 바이러스 예방을 위해 면접 대기실에서는 거리두기를 지켜야 하는데, 이 때, 각 면접실의 대기실 지원자들이 거리두기를 유지하였는지를 판단하는 문제

(맨해튼 거리가 2이하인 거리에 붙어 앉으면 거리 두기 위반이지만, 그 사이에 파티션으로 구분되면 거리 두기를 지킨 것)

 

 

2. 풀이

 

거리두기를 지켰는지 주변 대기자들과의 거리를 재고 그 거리가 적절한지를 판단하는 문제이다.

즉, 그래프 자료구조를 통해서 각 대기실의 면접자를 정점으로 인식한다면 그 거리를 간선으로 이해하고 상호 간의 거리를 측정하여 계산하면 된다.

 

거리두기의 규칙은 다음과 같다.

① 지원자간 맨해튼 거리가 2 이하이면 거리 두기 위반
   → 맨해튼 거리 : 각 위치가 (y1, x1), (y2, x2) 일 때 맨해튼 거리는 $|y2-y1| + |x2-x1|$ 이다.

② 지원자간 맨해튼 거리가 2 이하더라도 파티션으로 구분된다면 거리 두기를 지킨 것

 

풀이 방법은 다음과 같다.

BFS 또는 DFS를 통해 주변 지원자들과의 거리를 측정하여 맨해튼 거리가 2 이하인데 파티션으로 구분되지 않은 거리에 서로 앉아있다면 위반으로 반환.

여기서는 BFS를 통해 해결한 코드를 작성하였다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.util.*;
class Solution {
    int[] dy = {0, 1, 0};  // y축 이동 방향
    int[] dx = {1, 0, -1}; // x축 이동 방향
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for(int i=0; i < places.length; i++){
            answer[i] = solve(places[i]);
        }
        return answer;
    }
    
    private int solve(String[] place){
        for(int i=0; i < place.length; i++){
            for(int j=0; j < place[i].length(); j++){
                if(place[i].charAt(j) == 'P') { // 대기실 현재 면접자의 위치를 기반 BFS 탐색
                    int ans = bfs(place, i, j);
                    if(ans == 0) return 0;
                }
            }
        }
        return 1;
    }
    
    // BFS 탐색 수행하는 메소드
    private int bfs(String[] place, int y, int x){
        Queue<Pos> q = new LinkedList<>();
        boolean[][] visited = new boolean[5][5];
        q.add(new Pos(y, x));
        visited[y][x] = true;
        
        while(!q.isEmpty()){
            Pos c = q.poll();
            for(int i=0; i < dy.length; i++){
                int ny = c.y + dy[i];
                int nx = c.x + dx[i];
                int mhtDist = Math.abs(ny - y) + Math.abs(nx - x); // 맨해튼 거리 측정
                
                // 범위 벗어난 경우 / 맨해튼 거리가 2 초과인 경우 / 이미 방문된 경우 통과
                if(ny < 0 || ny >= 5 || nx < 0 || nx >= 5 || mhtDist > 2 || visited[ny][nx]) continue;
                
                visited[ny][nx] = true;
                if(place[ny].charAt(nx) == 'P') return 0;  // 다른 지원자가 있으면 위반
                else if(place[ny].charAt(nx) == 'X') continue; // 파티션이면 방문 불가
                else q.add(new Pos(ny, nx)); // 빈 책상이라면 다음 탐색을 위해 추가
            }
        }
        return 1;
    }
}
class Pos{
    int y;
    int x;
    public Pos(int y, int x){
        this.y=y;
        this.x=x;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.