[Programmers]2021 카카오 채용연계형 인턴십: 거리두기 확인하기(Python)/BFS

https://programmers.co.kr/learn/courses/30/lessons/81302?language=python3 

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

오랜만에 풀어본 파이썬 BFS 문제

아직은 C가 편하지만 파이썬은 리스트로 스택 큐 둘다 사용할 수 있어서 편한 것 같기도 ㅎ

모든 응시자(P)에 대해 BFS로 도달할 수 있는 거리 2 이내에 다른 사용자가 있는지 확인해주는 간단한 문제였다

def bfs(p, place):
    dr=[1,0,-1,0]
    dc=[0,1,0,-1]
    visit=[[False for _ in range(5)] for _ in range(5)]

    q=[p]
    visit[p[0]][p[1]]=True

    for _ in range(2):
      size=len(q)
      for _ in range(size):
        cur = q.pop(0)

        for i in range(4):
          nr=cur[0]+dr[i]
          nc=cur[1]+dc[i]

          if nr<0 or nr>=5 or nc<0 or nc>=5 or place[nr][nc]=='X' or visit[nr][nc] :continue
          if place[nr][nc]=='P': 
            return False

          q.append([nr,nc])
          visit[nr][nc]=True
    return True

def solution(places):
    answer = []
    for place in places:
      k=True
      for i in range(5):
        for j in range(5):
          if place[i][j]!='P': continue

          k=k&bfs([i,j], place)
      if k: answer.append(1)
      else: answer.append(0)

    return answer