백준 9466번 : 텀 프로젝트 in Python

9466번: 텀 프로젝트

 

www.acmicpc.net

이 문제는 텀 프로젝트를 수행하기 위해 학생들 간에 프로젝트 팀을 구성할 때, 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 구하는 문제이다. 단, 모든 학생은 프로젝트를 함께하고 싶은 학생을 한 명만 선택할 수 있고, 프로젝트 팀을 구성하기 위해서는 학생을 s_1, s_2, ... ,s_r이라 할 때 s_1은 s_2를, s_2는 s_3를, ..., 그리고 s_r은 s_1을 선택해야 (s_1, s_2, ... ,s_r)이 한 팀을 이룰 수 있다. r=1인 경우, 즉 s_1이 자기 자신을 택하는 경우도 포함한다.

이 문제는 설명이 복잡하지만 결국 구하고자 하는 것은 학생들을 그래프의 정점, 프로젝트를 함께하고 싶은 학생을 선택하는 것을 그래프의 간선이라고 생각하면, 그래프 내에서 사이클에 속하지 않는 학생의 수를 구하는 문제이다. 이는 DFS를 이용해 구할 수 있다.

우선 각 학생에 대해 조사했었는지를 나타내는 배열인 visited와 그 학생이 프로젝트 팀에 속하는지를 저장하는 배열인 inTeam을 만들고, 초기값으로 visited의 각 원소는 0, inTeam의 각 원소는 1로 한다. 그리고 모든 학생에 대해 순회하면서 아직 i번째 학생을 조사하지 않은 경우 DFS를 그 학생에 대해 수행한다.

이제 DFS 함수를 어떻게 구현할지를 살펴보자. 우선 해당 학생을 조사한다는 의미로 visited[i]를 1로 한다. 그리고 이 학생이 그래프 내 사이클에 속하는지를 나타내는 res라는 변수를 만들고 초기값은 False로 한다. 이제 i번째 학생이 선택한 학생의 visited 값이 1인지를 살펴본다. 이는 i번째 학생에서 i번쨰 학생이 선택한 학생으로 가는 간선이 back edge를 살펴보는 것이다. back edge란 그래프에서 탐색을 수행할 때 어떤 간선을 통해 자신의 ancester(조상 정점)을 만났을 때 그 간선을 말한다. 이는 그 간선으로 인해 사이클이 생겼다는 것을 의미한다. 왜냐하면 DFS를 수헹할 때 자신의 ancester부터 시작해 재귀적으로 DFS를 수행하는데, 만약 자기 자신을 다시 만난 경우 그 간선을 통해 다시 자기 자신으로 복귀할 수 있는 길이가 2 이상인 경로를 찾은 것이기 때문이다.(만약 i번째 학생이 택한 학생이 자기 자신인 경우에는 i번째 학생에 대한 loop가 있는 것으로, 엄밀히 말하면 이는 사이클은 아니지만 팀을 이룰 수는 있다.) 따라서 i번째 학생은 팀에 속하므로 res를 True로 바꾼다. 그리고 inTeam의 i번째 학생이 선택한 학생에 대한 entry를 0으로 한다. 이렇게 하는 이유는 나중에 설명한다.

만약 i번째 학생이 선택한 학생이 아직 조사하지 않은 학생이라면 그 학생에 대해 재귀적으로 DFS를 수행하고 그 결과 반환한 res 값을 현재 res에 저장한다. 이렇게 재귀적으로 함수를 호출하다보면 위 case에 속하는 경우까지 도달하는 경우와 그렇지 않은 경우가 있을 것이다. 만약 도달한 경우에는 반환값(재귀적으로 호출한 함수 내 res)이 True가 되어 현재 함수 내 res 값이 True가 될 것이고, 그렇지 않으면 반환값이 False가 되어 현재 함수 내 res 값이 False가 될 것이다. 이때 주의할 점이 있는데, 이 반환값이 True가 된다고 해서 반드시 이 학생이 사이클에 속한다고 보장할 수 없다는 점이다. 예를 들어 1 -> 4 -> 7 -> 6 -> 4로 학생들이 서로 선택을 했다고 가정하자. 만약 학생 1에 대해 DFS를 수행하면 6 -> 4가 back edge가 되어 DFS(6)에서 res가 True가 된다. 이를 재귀적으로 수행 중이었으므로 DFS(7), DFS(4), DFS(1)에서 모두 res가 True가 된다. 하지만 학생 1은 사이클에 속하는 학생이 아니다. 실제 사이클은 4 -> 7 -> 6 -> 4이기 때문이다. 그렇다면 학생 1은 어떻게 사이클에서 제외할 수 있을까? 여기서 back edge를 발견했을 때 굳이 inTeam의 i번째 학생이 선택한 학생에 대한 entry를 0으로 한 이유를 들 수 있다.

back edge를 발견했을 때 i번째 학생이 선택한 학생은 사이클 내 학생들 중 DFS 탐색을 가장 먼저 시작한 학생이다. 이 학생에 대한 entry를 0으로 바꾸는 것은 재귀적으로 호출된 DFS 함수를 빠져나올 때 어느 학생까지가 사이클에 속한 학생인지를 나타내는 방법인 것이다. 위 예시에서 6 -> 4가 back edge이므로 inTeam[4]를 0으로 해 두면 재귀적으로 호출되었던 DFS(6), DFS(7)을 반환하는 동안 inTeam[6], inTeam[7]은 1이므로 사이클이 끝나지 않았음을 알 수 있고, DFS(4)를 반환할 때 inTeam[4]는 0이므로 사이클이 끝났음을 알 수 있다. 여기서 res를 False로 반환하면 DFS(1)로 복귀했을 때 반환된 res 값이 False이므로 이 학생이 사이클에 속하지 않음을 알 수 있는 것이다. 

이제 이를 구체적으로 구현하면, res가 True이면서 inTeam[i]가 0이 아닌 경우에는 사이클에 속하면서 아직 사이클의 시작점에 도달하지 않았다는 것을 의미하므로 이 학생이 사이클에 속한다는 의미로 inTeam[i]를 0으로 한다. 그렇지 않은 경우에는 사이클에 속하지 않거나 사이클의 시작점에 도달했다는 것을 의미하므로 res를 False로 바꾼다. 그리고 이 학생에 대한 조사가 완전히 끝났다는 의미로 visited[i]를 2로 변경한다. 이는 DFS 함수에서 맨 처음에 back edge 여부를 조사할 때와 혼동되지 않도록 하기 위함이다. 마지막으로 res 값을 반환한다.

모든 학생에 대해 순회를 완료하면 inTeam에는 사이클에 속하는 학생은 0, 속하지 않는 학생은 1을 받게 된다. 따라서 inTeam의 모든 entry를 더하면 사이클에 속하지 않는 학생의 수를 구할 수 있다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
T = int(input())
# 사이클에 속하는지를 파악하기 위한 DFS 탐색 함수
def DFS(u):
    # 방문 직후임을 표시
    visited[u] = 1
    # 사이클에 속하는지를 나타내는 변수
    res = False
    # back edge 조사
    if visited[graph[u]] == 1:
        # 사이클 시작점 표시
        inTeam[graph[u]] = 0
        res = True
    # 재귀적으로 DFS 수행
    elif visited[graph[u]] == 0:
        res = DFS(graph[u])
    # 사이클에 속하면서 사이클의 시작점이 아닌 경우
    if res and inTeam[u] != 0:
        inTeam[u] = 0
    else:
        res = False
    # 해당 정점에 대한 조사가 완전히 끝났음을 표시
    visited[u] = 2
    return res
for _ in range(T):
    N = int(input())
    inTeam = [1 for _ in range(N+1)]
    visited = [0 for _ in range(N+1)]
    graph = [0] + list(map(int, input().split()))
    for i in range(1, N+1):
        if not visited[i]:
            DFS(i)
    # entry 계산의 편의를 위해 실제 구현할 때 배열 길이가 N+1이 되도록 설정했는데,
    # 이를 보정하기 위해 inTeam[0]=1을 빼준다.
    print(sum(inTeam) - 1)