[텀 프로젝트/G3/Python3]

9466번 텀 프로젝트 G3

 

문제
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어 하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2,..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. 주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 

그래프 이론, 그래프 탐색, 깊이 우선 탐색

 

진입 차수와 진출 차수를 이용하여 풀이를 진행했다.

 

모든 학생들은 프로젝트를 함께하고 싶은 학생을 1명 선택한다. (진출 차수는 1, 진입 차수는 ?)

역방향 간선의 경우에는 진입과 진출이 반대가 된다. (진입 차수는 1, 진출 차수는?)

 

방문 정보를 저장하기 위해 visited 변수를 사용했다.

미방문 : 0, 팀이 존재하지 않음 : -1, 팀이 존재하거나 방문 중 : 1

 

dfs의 실행 순서는 다음과 같다. 역방향 간선을 사용한다.

1. 진출 차수가 0이라면 팀이 존재하지 않는다.

2. 모든 방문 가능한 점의 팀이 존재하지 않으면 해당 정점도 팀이 존재하지 않는다.

3. 팀이 존재하는 정점이 존재하면 해당 정점도 팀이 존재한다.

 

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

def dfs(index):
    global visited
    visited[index] = 1

    if not r_routes[index]:
        visited[index] = -1
        return -1
    cnt = 0
    i_check = -1
    for j in r_routes[index]:
        if visited[j] == 1:
            i_check = j
        elif visited[j] == 0 and dfs(j) != -1:
            cnt += 1
    if cnt == 0 and i_check == -1:
        visited[index] = -1
        return -1
    return 1

for i in range(T):
    num = int(sys.stdin.readline())
    routes = list(map(int, sys.stdin.readline().split()))
    
    visited = [0 for _ in range(num+1)]
    r_routes = [[] for _ in range(num+1)]
    
    for end, start in enumerate(routes):
        r_routes[start].append(end+1)
        
    for j in range(1, num+1):
        if visited[j] == 0:
            dfs(j)

    no_cnt = 0
    for j in range(1, num+1):
        if visited[j] == -1:
            no_cnt += 1
    print(no_cnt)

 

 

 

SCC로도 풀이가 가능할 것 같아 코사라주의 알고리즘으로 풀이를 진행해 보았다.

 

import sys
sys.setrecursionlimit(10**6)

routes = []
r_routes = []
visit = []
stk = []

def dfs(v):
    temp.append(v)
    visit[v] = False
    for vv in r_routes[v]:
        if not visit[vv]: continue
        dfs(vv)

def dfs_stk(v):
    visit[v] = True
    if not visit[routes[v]]: dfs_stk(routes[v])
    stk.append(v)
    
for ___ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    routes = [-1] + list(map(int, sys.stdin.readline().split()))
    r_routes = [[] for _ in range(n+1)]
    visit = [False] * (n+1)
    stk = []
    
    for i in range(1, n+1):
        r_routes[routes[i]].append(i)
        
    for i in range(1, n+1):
        if visit[i]: continue
        dfs_stk(i)

    cnt = 0
    while stk:
        v = stk.pop()
        if not visit[v]: continue
        temp = []
        dfs(v)
        if len(temp) >= 2: continue
        if routes[temp[0]] == temp[0]: continue
        cnt += 1
    print(cnt)

 

---

 

처음 문제를 풀이할 때 사이클 판단에 어려움을 겪었던 기억이 난다.