[백준] 17352 여러분의 다리가 되어 드리겠습니다! - python

문제 링크
https://www.acmicpc.net/problem/17352

시도1. 실패

import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(n-2):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  
def dfs(start, temp):
  visited[start] = True
  temp.append(start)
  for v in graph[start]:
    if not visited[v]:
      dfs(v, temp)

map = []      
for i in range(1, n+1):
  if not visited[i]:
    temp = []
    dfs(i,temp)
    map.append(temp)

print(map[0][0], map[1][0])

• 접근 방법 : dfs
• Recursion error. N 이 30만까지 가능하므로 30만개의 recursion이 너무 많이 쌓여서 에러가 난다.

시도2. 성공

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(n-2):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  
def bfs(start, visited):
  temp = [start]
  visited[start] = True
  queue = deque(graph[start])
  while queue:
    current = queue.popleft()
    temp.append(current)
    visited[current] = True
    for i in graph[current]:
      if not visited[i]:
        queue.append(i)
  return temp

map = []
for i in range(1, n+1):
  if not visited[i]:
    map.append(bfs(i,visited))

print(map[0][0], map[1][0])

• 접근 방법 : bfs

시도3. 아직안해봄

dfs/bfs 가 아닌 훨씬 빠르게 푸는 방법이 있었다... 피곤하니까 내일 찾아서 적어야지