[백준] 16947번(서울 지하철 2호선)

백준 16947번

최종 제출 코드

import sys
from collections import deque
sys.setrecursionlimit(100000)

input = sys.stdin.readline

# 입력값 입력받기
n = int(input().rstrip())
array = [[] for _ in range(n+1)]

for i in range(n):
  a, b = map(int, input().split())
  array[a].append(b)
  array[b].append(a)
  
# bfs, dfs에 사용할 queue, stack, visited 선언
queue = deque()
stack = []
visited = [-1 for _ in range(n+1)]

# dfs함수 - 순환선을 구분하기 위한 함수
def dfs(index, start, depth):
  
  if depth >2 and index==start:
    for i in stack:
      if i not in queue:
        visited[i] = 0
        queue.append(i)
    return True
  
  for i in array[index]:
    if visited[i] == -1:
      visited[i] = 1
      stack.append(i)
      check = dfs(i,start,depth+1)
      if check: return True
      visited[i] = -1
      stack.pop()

  return False

# 각각의 노드를 시작점으로 잡고 순환경로가 있는지 dfs 실행
# dfs가 True를 return하면 반복문을 종료한다
for i in range(1, n+1):
  check = False
  stack.append(i)
  check = dfs(i,i,0)
  if check: break
  stack.pop()

# bfs실행 - 순환선까지의 거리를 탐색
while queue:

  element = queue.popleft()

  for index in array[element]:
    if visited[index] == -1:
      queue.append(index)
      visited[index] = visited[element] +1

# 결과출력
print(*visited[1:])

.

◼️ 순환선 탐색에는 dfs, 순환선까지의 거리 탐색에는 bfs를 사용해야함

• bfs로만 풀어보려다가 도저히 해답을 찾지 못해서 출처의 아이디어만 참고하였다.

.

◼️ DFS

• 시작점을 start 인수로 주고, 시작점의 visited 값은 변경하지 않는다.
  ⇒ 시작점을 다시 방문할 수 있게 하기 위함
• A → B → A는 순환경로가 아니다.
  ⇒ 탐색 경로의 길이가 2보다 클때만(depth > 2) 순환경로로 간주
• 위의 두 가지 조건을 만족하면 stack의 순열이 순환경로를 의미함으로 이를 queue에 append
  (start 노드는 stack 내에 중복됨으로 queue에 append 되지 않은 원소만 추가)
• 이 경우는 추후에 코드를 바꿔 실행했을 때 아래처럼 수정하는 것이 실행시간이 더 빨랐음

if depth > 2 and index==start:
    for i in stack[1:]:
      visited[i] = 0
      queue.append(i)
    return True

• 그러나 어째서인지 백준 채점 프로그램으로 돌리면 최종 제출 코드로 풀 때가 근소하게 더 빠르게 나옴

.
◼️ 시간초과

• 처음에는 순환선을 발견해도 탐색을 종료하지 않음
• 그러나 순환선은 1개만 존재함으로 순환선을 발견했다면 더 이상 dfs를 실행할 필요가 없음
• 따라서 dfs를 종료시키는 조건없이 모든 노드에 대해 dfs를 실행하면 시간초과가 발생하는 것
  (한 번 탐색에 들어가면 모든 노드와 경로를 탐색함으로 엄청난 시간 소요)
  ⇒ 순환선을 발견하면 True를 return해줘서 for문에서 호출한 dfs를 빠져나올 수 있게 해줬다