[백준알고리즘] 2252번: 줄 세우기 -Python

[백준알고리즘] 2252번: 줄 세우기 -Python

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

directed graph에서 tree를 만들면 되는 것 같다.

 

근데 정답비율을 보고 좀 의아했다. 이렇게 쉬운 문제인가..?

아무튼 생각이 안 나서 나는 찾아보고 풀었다. 통과한 코드는 위상 정렬을 사용한 방법이다.

위상 정렬에 대해서는 아래의 글을 참고했다.

https://terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093

 

진입 차수(in-degree)가 0인 곳들을 계속해서 시작점으로 경로들을 찾아갔다. 음.. 이 방법은 위의 글을 읽는 것이 훨씬 이해가 쉬울 것 같다.

 

위상 정렬을 이용한 방법말고 질문게시판에는 DFS로 풀었다는 글이 꽤 보였다. 통과한 코드에도 실제로 DFS를 사용한 코드가 많았다.

DFS를 이용한 방식으로는 문제를 안 풀어봤는데 이해한 바를 적어놔야겠다.

DFS로 풀 때에는 위상 정렬 때와 반대로 진출하는 노드들을 리스트로 저장하고 있는 것이 아니라 진입해오는 노드들에 대해서 리스트로 저장하고 있는다.

그리고 아직 방문하지 않은 점부터 자신에게 진입할 수 있는 노드들을 순차적으로 확인한다. 마찬가지로 방문하지 않았다면 해당 노드를 방문하고, 그 노드에서 자신에게 또 진입할 수 있는 노드들을 확인한다.

 

즉, 진입할 수 있는 노드들로 문제에서 주어진 방향과 반대로 DFS 한다. 예를 들어 아래의 경우를 확인하겠다.

Input :
4 4
2 1
2 4
1 3
4 3

이럴 경우 1~4번 노드는 각각 진입해오는 노드들을 기록하기 때문에 v[1] = [2], v[2] = [], v[3] = [1, 4], v[4] = [2]이다. 그리고 모든 점을 돌면서 DFS로 각 점의 상위 노드들을 확인해나간다.

 

뭐... 이정도만 하고 코드를 보면 이해는 될 것 같다.

 

아래는 위상 정렬로 푼 코드다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
inDegree = [0] * (n+1)
inDegree[0] = -1
direct = [[] for _ in range(n+1)]
queue = deque()

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    inDegree[b] += 1
    direct[a].append(b)

for i in range(1, n+1):
    if inDegree[i] == 0:
        queue.append(i)

while queue:
    q = queue.popleft()
    print(q, end=' ')
    for d in direct[q]:
        inDegree[d] -= 1
        if inDegree[d] == 0:
            queue.append(d)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다