[ 백준 2623번 ] 음악프로그램 파이썬

[ 백준 2623번 ] 음악프로그램 파이썬

[백준 2623번 음악 프로그램 바로가기]

1 큐를 이용한 위상정렬

논리

진입차수가 0인 노드를 큐에 넣는다 큐에서 꺼내면서 result에 순차적으로 기록하고, 해당 노드에 연결을 없앤다 연결이 해제된 노드들 중 새로 진입차수가 0이 된 노드를 큐에 넣는다 탐색 완료시 result의 개수가 총 노드의 개수보다 적으면 순환구조가 발생한 것이라 판단

2 dfs를 이용한 위상정렬

논리

진입차수가 0인 노드부터 dfs진행(방문한 노드 기록하여 중복된 방문 방지) 순환 구조 여부를 파악하기 위해 실시간 탐색 경로를 기록한다. 각 노드를 탐색할 때(진입 -> 하위 노드 탐색 -> 빠져나오기), 진입 단계에서 탐색경로에 추가하고, 빠져나올 때 탐색경로에서 제거한다 --> 다음 하위 노드가 탐색 경로에 존재하면 순환구조라고 판단 각 노드 탐색 완료시(빠져나올 때) result에 역순으로 기록한다

코드

import sys from collections import defaultdict, deque # using queue def music_queue(N, graph, in_degree): # enque nodes with 0 indegree q = deque() for node in range(1, N+1): if in_degree[node] == 0: q.append(node) # topological sorting using queue # remove nodes with 0 indegree --> enque new nodes with 0 indegree result = [] while q: curr = q.popleft() result.append(curr) for next in graph[curr]: in_degree[next] -= 1 if in_degree[next] == 0: q.append(next) if len(result) == N: print(*result, sep='

') else: print(0) return # using dfs(recursion) def music_dfs(N, graph, in_degree): def _dfs(curr): # 순환구조시 탐색 안함 if has_cycle[0]: return visited[curr] = True # 현재까지의 경로 기록 route.append(curr) for next in graph[curr]: # 순환구조 판단 if next in route: has_cycle[0] = True if not visited[next]: _dfs(next) # 노드 탐색 완료시 경로에서 pop하고, result에 추가 route.pop() result.append(curr) visited = [False] * (N+1) # 노드 방문 여부 기록 route = [] # 탐색 경로 기록 has_cycle = [False] # 순환구조여부 파악 result = [] for node in range(N+1): if not in_degree[node]: # 진입차수 0인 노드 탐색 _dfs(node) if has_cycle[0]: # 순환구조시 0 출력 print(0) else: # 역순으로 출력 print(*result[-1:-N-1:-1], sep='

') return ######################################################### # inputs N, M = map(int, sys.stdin.readline().split()) graph = defaultdict(list) in_degree = [0] * (N+1) for _ in range(M): nums = list(map(int, sys.stdin.readline().split())) for i in range(1, nums[0]): in_degree[nums[i+1]] += 1 graph[nums[i]].append(nums[i+1]) # 택 1 # music_queue(N, graph, in_degree) # music_dfs(N, graph, in_degree)

from http://realbro.tistory.com/11 by ccl(A) rewrite - 2021-08-25 15:27:33