けんさきょり

📌 質問リンク

市草。BFSアルゴリズム

import queue # bfs 탐색 시 사용하는 자료 구조

# 상하좌우 이동, 고정된 값이므로 tuple 사용
D = ((-1,0), (1,0), (0, -1), (0, 1)) # 위로 이동, 아래로 이동, 좌로 이동, 우로 이동

def bfs(place, row, col): # 대기실, 응시자의 위치 정보 
                        # -> 거리두기 확인 return 값 : True/False
    visited = [[False for _ in range(5)] for _ in range(5)] # 대기실 크기만큼의 방문 array
    q = queue.Queue() # queue 객체 생성
    visited[row][col] = True # 방문 표시
    q.put((row, col, 0)) # 행, 열, 거리(시작위치) tuple 형태로 입력
    
    while not q.empty():
        curr = q.get() # dequeue, 현재 좌표
        
        if curr[2] > 2 : # 거리가 2보다 클 경우 탐색 skip
            continue
        # 거리 2 이하인 경우
        if curr[2] != 0 and place[curr[0]][curr[1]] == 'P': # 다른 응시자를 만난 경우
            return False 
        # 거리 2 이하 & 다른 응시자를 만나지 않은 경우
        for i in range(4): # 상하좌우 이동
            nr = curr[0] + D[i][0]
            nc = curr[1] + D[i][1]
            if nr < 0 or nr > 4 or nc < 0 or nc > 4: # 대기실 밖일 경우
                continue
            if visited[nr][nc]: # 이미 방문한 경우
                continue
            if place[nr][nc] == 'X':
                continue
            visited[nr][nc] = True
            q.put((nr, nc, curr[2]+1))
    return True
            
            
def check(place):
    for r in range(5):
        for c in range(5):
            if place[r][c] == 'P':
                if bfs(place, r, c) == False: # bfs 호출 (거리두기 확인)
                    return False # 탐색 중단 -> answer = 0
    return True # 거리두기 모두 지키고 있는 경우 1

def solution(places):
    answer = []
    
    for place in places:
        if check(place): # 각 대기실 거리두기 확인
            answer.append(1)
        else:
            answer.append(0)
    return answer

🔎 リファレンス