[프로그래머스] 동굴 탐험, Python3

문제는 여기!

이번 문제는 꽤 어려웠다. 이 문제를 예전에 풀었던 적이 있어도 막상 다시 풀려고 하니까 기억이 나지 않아서 다른 분의 풀이를 보았다. 그 코드를 기반으로 어떻게 동작하는지 정리하고 풀어보았다.

• 제한사항 및 유의사항

  • n <= 200,000
  • path 배열의 원소는 [방번호A, 방번호B] 이며 이 두 방 번호는 순서를 보장하지 않는다.
  • order에서 [방번호A, 방번호B]의 의미는 A번방을 먼저 방문한 다음 B번방을 방문해야한다.

• 풀이전략

  • 우선 문제에서 양방향으로 방이 연결되어 있으므로 연결된 그래프를 표현하기 위해 path_dict 선언
  • wait, check list
    • wait 리스트는 해당 번호가 기다리고 있는지 체크하기 위한 배열이다. 기다리고 있을 경우 wait[node] = 1
    • check는 해당 노드가 방문했음을 표시해준다. 방문했을 경우 check[node] = 1
  • before, after dict
    • order에서 [A, B]는 B번방을 가기 전에 A번방을 방문해야 한다는 것을 뜻한다.
    • before는 방문할 방이 먼저 방문해야하는 방이 있는지 체크하기 위해 선언한 딕셔너리다.
      • before[B] = A 로 표현
    • after는 A번방에서 가야할 B번방이 있는지, 그에 따라 B번방을 탐방해야할지 말지를 체크하는 딕셔너리다.
      • after[A] = B 로 표현
  • BFS를 활용해 0번 방부터 탐방해준다.
    • 만약 큐에서 뽑힌 방번호가 이전에 방문해야하는 방이 있을 경우
      • wait 리스트에서 뽑힌 방번호 위치에 True로 변환
    • 또, 큐에서 뽑힌 방번호가 해당 번호 이후에 방문해야할 방번호가 존재하고 그 방문해야할 방번호가 대기중인 경우 바로 큐에 삽입한다.
    • path_dict[큐에서 뽑힌 방번호] = 해당 번호와 연결된 방들
      • 방문하지 않았을 경우 큐에 삽입
    • check[큐에서 뽑힌 방번호] = 1 처리
  • check 리스트의 합이 문제에서 주어진 n과 맞지 않을 경우 False, 맞을 경우는 True 반환

  from collections import deque
  def solution(n, path, order):
      wait, check = [False] * (n + 1), [0] * (n + 1)
      path_dict = dict()
  
      for x, y in path:
          if x in path_dict:
              path_dict[x].append(y)
          else:
              path_dict[x] = [y]
          if y in path_dict:
              path_dict[y].append(x)
          else:
              path_dict[y] = [x]
  
      before = {y: x for x, y in order}
      after = {x: y for x, y in order}
  
      q = deque()
      q.append(0)
      while q:
          now = q.popleft()
          # before[now] = now를 방문하기 전에 방문해야할 방
          # wait[now] = now가 먼저 방문해야 하는 방을 위해 대기중인지 체크
          # now를 대기중인 상태로 놓고 큐를 돌린다.
          if now in before and check[before[now]] == 0 and not wait[now]:
              wait[now] = True
              continue
          # now가 먼저 방문해야하는 방인지 체크한다
          # after[now] = now를 방문한 후 다음방
          # after[now]가 대기중이라면 큐에 먼저 넣어주기
          if now in after and wait[after[now]]:
              q.append(after[now])
  
          for nx in path_dict[now]:
              if check[nx] == 0:
                  q.append(nx)
          check[now] = 1
  
      return True if sum(check) == n else False