[프로그래머스] 거리두기 확인하기 (Python 파이썬)

https://programmers.co.kr/learn/courses/30/lessons/81302#fn1

코딩테스트 연습 - 거리두기 확인하기

문제 설명

대기실 상태가 그래프(배열)로 주어진다.

응시자 간 간격이 맨하튼 거리 2 이하인 경우를 방역수칙이 안지켜지고 있다고 하며

맨하튼 거리가 2 이상이거나 응시자 사이에 벽이 존재하는 경우 방역수칙을 지키고 있다고 한다.

 

대기실의 그래프가 주어졌을 때,

방역수칙을 지키고 있는지, 없는지를 확인하는 문제이다.

---

풀이 과정

이 문제를 카카오테스트에서 직접 풀었을 때는 DFS를 이용하였고

다시 풀 때는 BFS를 이용하였다.

 

BFS를 이용했을 때가 훨씬 간결하기도 하였고 풀이 방법도 더 좋은 것 같아

BFS를 이용해 풀이를 하려고 한다.

 

먼저 대기실은 5개 이며

각각의 대기실은 5 x 5 배열로 이루어져 있다.

 

그리고 1번째 대기실부터 확인해보자.

대기실에 응시자(P)가 발견되면 그 응시자를 기준으로 맨하튼 거리 이내에 BFS를 수행하여

거리두기가 지켜지고 있는지 확인하자.

 

먼저, bfs함수 내의 visited를 통해 한 번 방문했던 칸은 방문하지 않도록 할 것이다.

한번 더 방문하게 되면 while문을 두 번 돌았을 때, 맨하튼거리 2 이상을 보장하지 못한다.

ex) 오른쪽으로 갔다가 다시 왼쪽으로 오는 경우는 제자리

 

시작칸을 기준으로 bfs를 수행하며

거리 1(상하좌우) 이내에 'P'(또 다른 응시자)가 발견되면 즉시 False를 리턴하자.

방문한 지점이거나 벽이 있는 경우는 무시하자. ( 아직 거리두기를 침해하지 않았으므로 )

 

그 외에, 거리 1 이내에 'O'가 있는 경우는 다음 칸을 한 번 더 검사해야 하므로

그 지점을 큐에 넣어주자.

 

그리고, 처음 응시자(시작점) 기준으로 2바퀴를 돌았을 때는 맨하튼 거리 2를 넘어가게 되므로

이 때까지 False를 리턴하지 않았다면 거리두기를 잘 지킨 것이므로 True를 리턴해준다.

 

이렇게 각각의 P마다 bfs를 수행하여 그 대기실의 모든 P가 거리두기를 잘 지킨다면

그 대기실에 1을 표시한다.

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(candidate, place):
    queue = deque()
    visited = [[False]*5 for _ in range(5)]
    queue.append(candidate)
    cnt = 0
    
    while queue:
        x, y = queue.popleft()
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if visited[nx][ny]:
                continue
            if place[nx][ny] == 'X':
                continue
            if place[nx][ny] == 'P':
                return False
            queue.append((nx, ny))
        
        cnt += 1
        if cnt == 2:
            return True
    return True
            

def solution(places):
    answer = []
    
    for place in places:
        candidates = deque()
        flag = True
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    candidates.append((i, j))
        
        for candidate in candidates:
            if not bfs(candidate, place):
                flag = False
                break
        
        if not flag:
            answer.append(0)
        else:
            answer.append(1)
        
    return answer

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !