PS/Python
[Python] 백준(BOJ) 9466번: 텀 프로젝트 - 스택, dfs
yoo.o
2020. 11. 6. 02:35
반응형
문제
9466번: 텀 프로젝트
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을
www.acmicpc.net
풀이
재귀를 사용하는 방법이기 때문에 recursion limit을 충분히 설정해주지 않으면 런타임에러가 난다.
스택과 dfs를 사용해서 풀었는데 조금 더 효율적인 방법이 있을것 같다.
import sys
sys.setrecursionlimit(10**8)
# 테스트 케이스 개수
T = int(sys.stdin.readline())
def dfs(i):
stack.append(i)
# 아직 방문 안했으면
if visited[students[i]] == 0:
visited[students[i]] = 1
dfs(students[i])
# 방문한애를 만나면 (싸이클)
elif visited[students[i]] == 1:
flag = 0
while stack:
now = stack.pop()
if now != students[i] and flag == 0:
visited[now] = 2
elif now == students[i]:
visited[now] = 2
flag = 1
else:
visited[now] = -1
else:
while stack:
now = stack.pop()
visited[now] = -1
# 각 테스트케이스마다
for _ in range(T):
# 학생의 수
n = int(sys.stdin.readline())
# 방문 배열
visited = [0 for _ in range(n+1)]
# 선택한 사람
students = list(map(int, sys.stdin.readline().split(" ")))
students.insert(0, 0)
stack = []
for i in range(1, n+1):
if visited[i] == 0:
visited[i] = 1
dfs(i)
count = 0
for each in visited:
if each == -1:
count += 1
print(count)
반응형