백준 9466 텀 프로젝트 파이썬
접근
dfs로 탐색을 하다 탐색한 부분이 다시 발견되면 cycle 이 성립한다. directed-graph 이기에 가능한 성질이다.
사고
단방향 그래프를 많이 다뤄보지 않아서 시간이 걸렸다. 처음에는 깊이 우선으로 탐색하다 방문한 곳이 나온다면 그 자리부터 한 바퀴를 세 주는 방법을 고려했다. 하지만 하나의 방문 확인 리스트로는 그 자리가 사이클 탐색까지 완료한 자리인지 아니면 사이클이 시작되는 자리인지 판단할 수 없다. 그래서 각각의 dfs가 시작될 때 temp_visited 를 따로 선언해주고 dfs 가 끝나면 temp_visited 에 들어간 자리들을 global_visited 에서도 업데이트해주었다. 우회적인 방법이라 판단되어 더 좋은 접근법이 얼마든지 있을 것 같다.
생각할 점
파이썬의 메모리 효율에 익숙치 않다. 예를 들어 visited 검사를 할 때, set와 list 무엇을 쓸지 항상 고민한다. 자바에서는 인덱싱이 한번에 되면 array, array 를 스캔할 일이 많을 때는 set 를 쓰면 됐는데 파이썬은 그 경계가 좀더 모호한 것 같다.
인덱싱을 0-base 로 바꾸어 처리했는데 문제 유형에 따라 이런 방식이 더 복잡할 수 있을것 같다. 디버깅도 헷갈릴 수 있다.
import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
def solve(lst):
n = len(lst)
v = [False] * n
cnt_prev_link = [0] * n
for i in range(n):
to = lst[i] - 1 # we use 0-base indexing
cnt_prev_link[to] += 1
cycle = [0] * n
for i in range(n):
if not v[i]:
c = i
temp_v = set()
temp_v.add(c)
nxt = lst[c] - 1
while (not v[nxt]):
if nxt in temp_v: # cycle found
while (cycle[nxt] == 0):
cycle[nxt] = 1
nxt = lst[nxt] - 1
break
temp_v.add(nxt)
nxt = lst[nxt] - 1
for a in temp_v:
v[a] = True
print(cycle.count(0))
for _ in range(T):
N = int(input())
solve(list(map(int, input().split())))
