백준 17199번
https://www.acmicpc.net/problem/17199

문제

후기

⏰ 풀이시간 20분 ++⏰

맞힌 사람이 많지 않은 그래프 문제를 풀기 위해 풀은 사람이 적은 순으로 정렬해서

찾은 문제의 3번째다.

문제의 결론을 이야기 하자면,

임의의 정점 "i" 에서 출발하여, 자신을 제외한 모든 정점에 방문할 수 있는 i를 출력하는 문제다.

이에 따라 그래프에 요소를 추가해주고, 모든 정점에서 출발할 때 마다 visited를 초기화하며

해당 조건이 가능한 i를 찾았을 때 출력하면 된다.

나의 풀이

import sys
input= sys.stdin.readline
sys.setrecursionlimit(10**7)

N = int(input())
graph = [[] for _ in range(N+1)]


for _ in range(N-1):
  a,b = map(int,input().split())
  graph[b].append(a) #그래프에 요소 추가

def dfs(v):
  visited[v] = True
  for i in graph[v]:
    if not visited[i]:
      dfs(i)
      visited[i] = True

for i in range(1,N+1):
  visited = [False] * (N+1) #매번 visited 를 초기화하며
  if not visited[i]: 
    dfs(i)
  if visited.count(True)==N: #i에서 시작한 dfs가 모든 그래프를 돌 수 있으면
    print(i) #해당 i를 출력하고 종료한다.
    exit()

print(-1) #만족하는 i가 없으면 -1을 출력한다.