[BOJ](Python) 백준 9466번: 텀 프로젝트

문제

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

9466번: 텀 프로젝트

주제	방향 그래프 & DFS
시간 / 메모리 제한	3초 / 256MB
정답 비율	24.043%

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행한다.

• 프로젝트 팀원 수에는 제한이 없다.
  • 모든 학생들이 동일한 팀의 팀원인 경우처럼 한 팀만 있을 수도 있다.

프로젝트 팀을 구성하기 위해 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택한다.

• 각자 단 한 명만 선택할 수 있다.
• 혼자 하고 싶은 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이 s1, s2, ..., sr이라 할 때, 아래의 경우에만 한 팀이 될 수 있다.

• r=1이고 s1이 s1을 선택하는 경우
• s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우

예를 들어, 한 반에 7명의 학생이 있고 아래와 같이 지목을 했을 경우를 생각해보자.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

위의 경우는 아래의 그림과 같은 연결 상태가 된다.

이 경우 (3), (4, 6, 7)이 한 팀을 이루고 1, 2, 5의 경우 팀을 이루지 못한다.

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

• 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다.
• 각 테스트 케이스에 둘째 줄에는 선택된 학생들의 번호가 주어진다.

출력

각 테스트 케이스마다 한 줄에 출력하고,

각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

- 예제 입력 1

2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

첫 번째 경우

두 번째 경우

- 예제 출력 1

3
0

풀이

이 문제는 그래프의 연결 관계를 보고 학생들의 팀 구성 상황에 대한 답을 내면 되는 문제이다.

그리고 각 학생이 다른 학생을 선택하는 것으로 방향이 생기게 되므로 특히 방향 그래프에 대한 문제이다.

방향 그래프를 그리며 이 방향 그래프의 연결 관계가 cycle을 이룬다면 한 팀으로 생각하면 된다.

cycle과 같은 그래프 용어에 대한 설명은 아래의 글을 참고하면 된다.

https://classic-griver.tistory.com/185

[알고리즘](C언어) 그래프 알고리즘

 

결과적으로 방향 그래프 연결관계에서 cycle을 이루지 않는 학생의 수를 구하는 문제이다.

 

사이클(Cycle)

각 vertex가 사이클을 이루는지 이루지 않는지 판별하는 함수를 만든다면 이 문제를 풀 수 있다.

사이클은 경로를 따라 가다보면 결국 자기 자신으로 돌아오게 되는 특징을 가지고 있다.

 

모든 vertex를 순회하며,

• 해당 vertex에서 출발해 인접 vertex로 계속 이동했을 때 최종 vertex가 자기 자신이 되면 cycle,
• 더이상 인접 vertex가 존재하지 않거나 최종 vertex가 자기 자신이 아니면 비cycle로 판단한다.

반복문을 이용한 사이클 판단(반복문을 이용한 DFS)

이 특징을 이용해 제작한 함수는 아래와 같다.

    for i in range(n):
        cycle = 0
        adj_vtx = g.adj_list[i][0]
        for _ in range(n):
            if adj_vtx == i:
                cycle = 1
                break
            adj_vtx = g.adj_list[adj_vtx][0]
        if cycle == 0:
            num += 1

n개의 vertex를 직접 순회하며,

해당 vertex의 인접 vertex로 계속 이동한다.

이동하며 해당 vertex로 돌아오면 return으로 종료하고,

n번의 이동이 끝날 때까지 돌아오지 못하면 반복을 종료한다.

돌아오지 못한 경우 cycle이 없는 것으로 생각하여 num에 1을 더해준다.

의미상으로 DFS에 해당하며 반복문을 이용해 구현한 것을 알 수 있다.

 

각 학생은 단 한 명의 학생만 지목할 수 있기에 이렇게 전체적인 코드를 작성할 수 있다.

import sys


class Graph:

    def __init__(self, vertex_num=None):
        # 인접 리스트
        self.adj_lsit = []
        self.vtx_num = 0

        self.vtx_arr = []

        if vertex_num:
            self.vtx_num = vertex_num
        self.vtx_arr = [True for _ in range(self.vtx_num)]
        self.adj_list = [[] for _ in range(self.vtx_num)]

    def add_vertex(self):
        self.adj_list.append([])
        self.vtx_num += 1
        self.vtx_arr.append(True)
        return self.vtx_num - 1

    def add_edge(self, u, v):
        self.adj_list[u].append(v)


T = int(sys.stdin.readline().strip())

for _ in range(T):
    n = int(sys.stdin.readline().strip())
    num = 0
    l = list(map(int, sys.stdin.readline().strip().split()))
    g = Graph(n)
    for i in range(n):
        g.add_edge(i, l[i] - 1)

    # cycle
    for i in range(n):
        cycle = 0
        adj_vtx = g.adj_list[i][0]
        for _ in range(n):
            if adj_vtx == i:
                cycle = 1
                break
            adj_vtx = g.adj_list[adj_vtx][0]
        if cycle == 0:
            num += 1
    print(num)

그렇지만 이런 식으로 작성할 경우 시간 초과가 발생하였다.

 

시간 초과가 발생한 이유를 생각해본 결과 반복문으로 DFS를 구현한 것이 시간 복잡도 상에서 손해일 수 있겠다고 생각되었다.

이에 재귀를 이용해 DFS를 구현하여 cycle을 판단하는 것이 낫다고 생각하였다.