백준 2623번: 음악프로그램 (파이썬, 위상정렬, Cycle)

유향그래프를 정렬하는 문제이고 사이클이 없으므로 위상정렬을 이용하여 풀었다.

 

앞서 푼 '2252번: 줄세우기' 문제와 사이클이 존재할 때와 존재 안할 때를 판별하는 것이 차이점이 였다. 위상 정렬을 하기 위해서는 사이클이 없어야 하므로 문제의 조건을 하나 추가한 것 같다.

 

위상정렬은 DFS로 그래프를 정렬 후 뒤짚는 방식으로 구현하였다.

 

사이클 판별은 두가지로 해보았다. 첫번째 방법은 노드  수 N과 크기가 같은 boolean 배열을 하나 만들어서 V의 종단노드부터 boolean 배열의 원소 값을 True로 한다. 그 후 종단노드의 부모노드 순으로 boolean 배열의 원소 값을 True로 한다.

이때 부모노드의 boolean 배열의 원소값이 False라면 Cycle이 존재한다고 판별하는 방법이다. 왜냐하면 cycle이 존재한다면 자식노드와 부모노드가 같기 때문이다. 

코드는 다음과 같다.

import sys


def dfs(n):
    visited[n] = True
    for child in tree[n]:
        if not visited[child]:
            dfs(child)
        elif not finished[child]:  # 부모 노드가 finished[child] = True가 아니다 -> 자식 노드에서 다시 방문하였다 -> cycle 존재
            print(0)
            sys.exit(0)
    rslt.append(n+1)
    finished[n] = True  # 자식 노드부터 finished[n] = True



N, M = map(int, sys.stdin.readline().split())

tree = [[] for _ in range(N)]
visited = [False for __ in range(N)]
finished = [False for ___ in range(N)]
rslt = []

for _ in range(M):
    list_ = list(map(int, sys.stdin.readline().split()))
    for i in range(list_[0]-1):
        tree[list_[i+1]-1].append(list_[i+2]-1)

for j in range(N):
    if not visited[j]:
        dfs(j)

rslt.reverse()

for k in rslt:
    print(k)

   

아래 그림은 간단한 유방향 그래프와 visited, finished배열의 원소들을 나타내 cycle 판별법 이해를 돕기 위해 그려보았다.

유방향 그래프에서 cycle 판별법 도식도 (위: cycle x, 아래: cycle o)

 다음으론 좀 더 직관적인 코드이다.

set을 이용하여 방문한 노드들을 set에 추가하고, 새로운 노드가 이미 방문한 노드들의 집합에 존재할 때 cycle이 존재한다고 판별하는 방법이다. 물론 set 대신 stack을 사용해도 된다.

이 코드로는 처음에 틀렸었는데 그 이유는 dfs가 끝날때 자식노드를 집합에서 제거하지 않았기 때문이다.

왜나하면 부모 노드가 여러 개일수도 있기 때문이고, 그렇다 하더라도 사이클이 존재 하는것은 아닌데 자식 노드가 다시 호출되고 자식노드는 이미 set에 있기 때문에 사이클이 존재한다고 잘못  판별하기 때문이다.

set을 이용해 cycle을 판별한 코드는 다음과 같다.

 

import sys


def dfs(n):
    visited[n] = True
    cycle.add(n)
    for child in tree[n]:
        if child in cycle:
            print(0)
            sys.exit(0)
        if not visited[child]:
            dfs(child)
    rslt.append(n+1)
    cycle.remove(n)  # 자식 노드를 set에서 제거(종단부터)


N, M = map(int, sys.stdin.readline().split())

tree = [[] for _ in range(N)]
visited = [False for __ in range(N)]
rslt = []

for _ in range(M):
    list_ = list(map(int, sys.stdin.readline().split()))
    for i in range(list_[0]-1):
        tree[list_[i+1]-1].append(list_[i+2]-1)

for j in range(N):
    if not visited[j]:
        cycle = set()
        dfs(j)

rslt.reverse()

for k in rslt:
    print(k)

 

set을 이용한 유향 그래프에서 cycle 판별 도식도(위: cycle x, 아래: cycle o)