[BOJ 24526] 백준 24526번 - 전화 돌리기

		2022 성균관대학교 프로그래밍 경진대회 Open Contest 풀이
A		[BOJ 24523] 내 뒤에 나와 다른 수
B		[BOJ 24524] 아름다운 문자열
C		[BOJ 24525] SKK 문자열
D		[BOJ 24526] 전화 돌리기
E		[BOJ 24527] 이상한 나라의 갈톤보드

1. 문제

$24526$. 전화 돌리기 (2022 성균관대학교 프로그래밍 경진대회 Open Contest D번)

백준 24526번 - 전화 돌리기 (https://www.acmicpc.net/problem/24526)

2. 풀이

어떻게 전화를 넘기더라도 한 사람이 두 번 이상 전화를 받는 경우가 발생하지 않아야 한다는 것은, 시작점에서 모든 경로를 향해 이동했을 때 사이클을 만나면 안됨을 의미한다.

이는 곧 사이클과 그 사이클에 도달하는 모든 노드들이 회장이 전화를 넘길 수 없는 부원이라는 말과 같다. (사이클에서 더 이동하여 도달하는 노드와는 연관이 없다.)

모든 노드에서 검사해야 하는데 $N\leq 100,000$에 $M\leq 500,000$이고 시간제한이 $1$초이므로 tree dp가 필요하다.

각 노드에서 뻗어 나가면서 사이클을 하나라도 만났다면 해당 노드와 거슬러 올라가는 노드의 dp를 모두 false로 만들어준다. 그리고 이미 dp값을 갖고 있다면, 탐색하지 않고 바로 그 값을 return한다.

3. 채점 결과

4. 회고

.

5. 코드