[Python - DFS] 9466 텀 프로젝트

📌 문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1234567

3

1

3

7

3

4

6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

📌 입력

content

📌 출력

content

📌 문제 풀이

👨‍🏫 접근

사이클을 찾는 문제. 사이클은 대개 DFS 등 재귀를 통해서 종종 구현하는 편이다. 이 문제가 어려웠던 점은 사이클을 구현하고 값을 구해도 값을 구하는 과정에서 시간 소요를 최소한으로 해야 했기 때문이다.

시간 초과를 최소화 하기 위해서 방문 처리를 어떻게 완료할 것인지 확실히 작성해야 한다. 이미 탐색하면서 사이클이 확인되었다면, 다음 탐색에서 그 사이클을 다시 분석하여 시간을 다시 소요하는 불필요한 과정을 없앤다.

👨‍🏫 문제 풀이

📄 전체 코드

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

t = int(input())


def check_team(k):  # k: 현재 노드
    global cnt

    visited[k] = True
    next = member[k]

    if not visited[next]: # 아직 방문하지 않았다면
        check_team(next)

    elif not done[next]:
        j = next
        while j != k:
            cnt += 1
            j = member[j]
        cnt += 1

    done[k] = True # 현재 노드는 완료 처리


for _ in range(t):
    n = int(input())
    member = [0] + list(map(int, input().split()))
    visited = [False] * (n + 1)
    done = [False] * (n + 1)

    cnt = 0

    for i in range(1, n + 1):
        if not visited[i]:
            check_team(i)

    print(n - cnt)

📄 준비

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

t = int(input())

...

for _ in range(t):
    n = int(input())
    member = [0] + list(map(int, input().split()))
    visited = [False] * (n + 1)
    done = [False] * (n + 1)

    cnt = 0

    for i in range(1, n + 1):
        if not visited[i]:
            check_team(i)

    print(n - cnt)

재귀가 상당히 여러 번 진행되기 때문에 재귀 한계를 늘려준다. 그리고, 방문처리를 한 다음에 값을 구하는 과정이 구현되어야 해서 구현 완료를 했는지에 대한 여부를 담을 테이블도 생성해주도록 했다.

그리고 최종적으로 이미 방문을 했다면 다시 사이클을 확인하지 않도록 하기 위해 방문하지 않았을 때만 알고리즘을 실행하도록 하였다.

📄 풀이

def check_team(k):  # k: 현재 노드
    global cnt

    visited[k] = True
    next = member[k]

    if not visited[next]: # 아직 방문하지 않았다면
        check_team(next)

    elif not done[next]:
        j = next
        while j != k:
            cnt += 1
            j = member[j]
        cnt += 1

    done[k] = True # 현재 노드는 완료 처리

이 과정에서 중요한 것은 다음 방문할 값인 next와 현재의 값인 k이다. 둘을 헷갈리지 않고 잘 구분해서 식을 작성한다. 일단 방문했는지의 여부를 체크한 다음, DFS를 실행한다.

모두 체크한 후에는 이 과정에 대해서 값을 구하는 과정을 실행했는가에 대한 여부를 확인한다. 만약 그렇지 않았다면, 값을 구해준다. 이때 구할 값은 사이클을 만들었을 때, 몇 번의 노드를 거치는지 즉, 몇 명이 팀을 꾸렸는지를 확인하는 것이다. 자신을 포함하여 모든 노드를 체크하면, 본인을 완료 처리 해준다.

📌 총평

거의 하루 종일 풀었다. 아직 구현력이 많이 부족한 듯하다. 보완해야겠다.