[파이썬] 백준 1471번 - 사탕 돌리기

https://www.acmicpc.net/problem/1471

티어: 플래티넘 4

 

 

 

로직

흔한 다른 SCC 문제와는 다르게, 문제에서 딱히 그래프라고 주어진게 없습니다.

그래프 먼저 만들어야 문제가 쉬워집니다.

먼저, n + 1 크기의 1차원 정수 배열 graph를 만들고, 0으로 초기화합니다.

graph[a]는 a번 칸에 있을 때, 다음으로 방문할 칸의 번호를 나타냅니다.

1부터 n+1까지 for문을 돌리며 graph 값을 지정해줍니다.

만들어진 그래프를 SCC 단위로 분리해줍니다.

 

다음으로, n + 1 크기의 1차원 정수 배열 dp를 만들고, -1로 초기화합니다.

dp[a]는 a번 칸에서 방문할 수 있는 칸의 최대 개수를 의미합니다.

크기가 2 이상의 SCC 안에 포함되는 칸은 dp값을 그 SCC의 크기로 지정해줍니다.

 

1부터 n+1까지 for문을 돌리며, dp값이 -1이 아니라면 dfs를 돌립니다.

dfs는 우선, 다음 방문할 노드를 정하고 다음과 같은 동작을 합니다.

1. 시작 노드와 다음 노드가 같다면(무한루프) dp[시작 노드]값을 1로 지정해줍니다.

2. dp[다음 노드]값이 -1이 아니라면, 이미 계산이 된 것이므로 dp[시작 노드]값을 dp[다음 노드] + 1로 지정합니다.

3. 둘 다 아니라면, 다음 노드의 값도 계산이 필요하므로 dp[시작 노드]값을 dfs(다음 노드) + 1로 지정합니다.

4. dp[시작 노드]값을 리턴합니다.

 

dp의 값들 중 가장 큰 값이 정답이 됩니다.

재밌다