거리두기 확인하기

문제

[문제]

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

from collections import deque

def bfs(p):

    start = []
    visited = [[0]*5 for _ in range(5)] # 방문처리 리스트
    distance = [[0]*5 for _ in range(5)] # 경로 길이 리스트
    
    for i in range(5): # 시작점이 되는 P의 좌표 구하기 
        for j in range(5):
            if p[i][j] == 'P':
                start.append([i,j])
    
    for s in start: # 시작점 하나씩 꺼내서 

        que = deque([s]) # 하나씩 꺼낸 시작점을 큐에 넣고
        visited[s[0]][s[1]] = 1 # visited 리스트에는 방문 처리
        
        while que:
            dx = [-1,1,0,0]
            dy = [0,0,-1,1]
            
            y, x = que.popleft()
            
            for i in range(4): # 상, 하, 좌, 우 체크
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0 <= nx < 5  and 0 <= ny < 5 and visited[ny][nx] == 0: # 방문한 적 없고 리스트를 벗어나지 않는 범위 내에서 탐색 
                    
                    if p[ny][nx] == 'O': 
                        visited[ny][nx] = 1
                        distance[ny][nx] = distance[y][x] + 1 
                        que.append([ny, nx])
                        
                    if distance[y][x] <= 1 and p[ny][nx] == 'P': # 상 하 좌 우 검색 중 P가 발견 & 경로 길이 리스트가 1보다 작을 경우 거리두기 실패
                        return 0
                        
    return 1 # 아무 문제 없이 for문을 모두 끝마쳤다면 거리두기 성공
                    
def solution(places):
    answer = []
    for i in places:
        answer.append(bfs(i))
        
    return answer
    

문제풀이

bfs 문제가 아직 익숙하지 않은 상태여서 그런지 풀이 아이디어가 잘 생각나지 않았다.
핵심 아이디어는
1. 탐색을 시작할 P의 자표를 이용하는 것
2. 방문한(채크한) 좌표는 중복해서 체크하지 않도록 visited 리스트를 활용한 것
3. distance 경로 길이 리스트를 활용해서 다른 P와의 거리를 체크하는 것

이다.