[programmers 81302] 2021 인턴쉽 2번 거리두기 확인하기

문제

[programmers 81302] 거리두기 확인하기

처음에는 combinations로 P 2개씩 짝지은 모든 경우 완전 탐색하려고 했는데
그럴 경우 칸막이 처리하기가 좀 까다로움.. 그래서 bfs로 구현함

풀이(bfs)

코드

from collections import deque

# P가 거리두기 지키고 있으면 True, 아니면 False 리턴함
# bfs 탐색
# cnt는 (r,c)~(x,y)까지의 거리 ( (nx,ny)이 아님에 유의)
def distance(r,c,board):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    q = deque()
    visited = [ [False]*5 for _ in range(5)]
    q.append((r,c,0))
    visited[r][c]=True

    while q:
        x,y,cnt = q.popleft()
        for dir in range(4):
            nx,ny = x+dx[dir],y+dy[dir]
            
            # 범위 벗어나거나 이미 방문한 경우
            if nx<0 or nx>=5 or ny<0 or ny>=5: continue
            if visited[nx][ny]: continue
            
            # 파티션이 있거나 맨해튼 거리가 2 초과인 경우 더 볼 필요없음
            if board[nx][ny]=="X": continue
            if cnt>2: continue
            
            # 사람이 있고 현재 cnt가 2 미만이면 거리두기 지키지 않은 것!
            if board[nx][ny]=="P" and cnt<2:
                return False
            
            q.append((nx,ny,cnt+1))
    
    return True
            

def solution(places):
    ans = [1]*len(places)
    for (idx,place) in enumerate(places):
        for loc in range(25):
            r,c = loc//5, loc%5
            if place[r][c]=="P":
                if not distance(r,c,place[:]): # 거리두기 지키고 있지 않으면
                    ans[idx]=0
                    break
                    
    return ans