BOJ 3182 - 한동이는 공부가 하기 싫어!

문제

N명의 선배가 각각 한 명의 다른 선배를 추천한다. 각 사람에서 출발하여 추천 체인을 따라갈 때, 가장 많은 사람을 만날 수 있는 출발점을 구하라.

입력

선배 수 N과 각 선배가 추천하는 선배 번호가 주어진다.

출력

가장 많은 사람을 만날 수 있는 선배 번호를 출력한다.

예제

입력	출력
`4` `2` `3` `4` `1`	`1`

풀이

각 출발점에서 체인을 따라가며 방문한 사람 수를 센다.

각 사람 i에서 출발하여 추천 체인을 따라간다
이미 방문한 사람을 만나면 멈추고 방문 수를 기록한다
방문 수가 최대인 출발점을 출력한다

핵심 아이디어: 각 노드에서 시작하는 체인은 반드시 사이클로 끝나므로, 방문 체크로 종료 조건을 판단한다.

코드

import sys
 
sys.setrecursionlimit(2000)
 
n = int(input())
next_senior = [0] + [int(input()) for _ in range(n)]
visited_count = [0] * (n + 1)
 
 
def dfs(start, visited):
    count = 0
    current = start
    while not visited[current]:
        visited[current] = True
        count += 1
        current = next_senior[current]
    return count
 
 
max_count = -1
answer = 0
 
for i in range(1, n + 1):
    visited = [False] * (n + 1)
    count = dfs(i, visited)
    visited_count[i] = count
    if count > max_count:
        max_count = count
        answer = i
 
print(answer)

복잡도

시간: O(N²)
공간: O(N)

문제