백준 2252 줄 세우기 문제풀이

문제 

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

2252번: 줄 세우기

 

 

 

문제 접근 방식

모든 학생의 키가 주어지는 것이 아니라 제공되는 두 학생의 위치관계를 사용하여 줄을 세워야한다. 학생들간 의존성이 주어지며 이를 해결하기 위해 위상정렬(Topological Sorting)을 사용하였다. 

 

위상 정렬의 기본적인 처리 과정은 아래와 같다.

1. 진입차수가 0 인 노드를 큐에서 꺼낸다.(방문 후 노드를 제거한다고 생각하면 된다)
2. 해당 노드와 이웃한 노드를 순회한다.
    2.1. 이웃한 노드의 진입차수를 1 감소시킨다.
    2.2. 진입차수가 0이 되면 큐에 해당 노드를 넣는다.

 

위와 같이 계속해서 진입차수를 0으로 만들어서 선행되어야하는 노드를 우선적으로 선택한다. 

 

 

시간 복잡도

모든 노드(V개)를 순회해야하며, 이때 이웃한 간선을 순회해야하기 때문에 전체 간선(E)을 모두 돌아야한다. 그래서 전체 시간복잡도는 O(V+E) 이고 V=32,000, M= 1e5이기 때문에 시간내에 동작한다.

 

 

코드

import sys
input=sys.stdin.readline

if __name__=='__main__':
    n,m=map(int,input().split())
    in_degree=[0]*(n+1)
    adj=[[] for _ in range(n+1)]
	
    # 인접 행렬을 초기화하고, 이때 진입차수도 같이 초기화해준다
    for _ in range(m):
        a,b=map(int,input().split())
        adj[a].append(b)
        in_degree[b]+=1


    answer=[]

    # 진입 차수가 0인 것, 즉 시작 노드가 가능한 것들을 큐에 넣어준다.
    q = []
    for i in range(1,n+1):
        if in_degree[i]==0:
            q.append(i)

    while q:
        now=q.pop(0)

        # answer에 노드를 넣어준다(방문해서 끝난 노드임)
        answer.append(now)

        # 이웃한 노드들의 진입차수를 1 감소 시킨다.
        # 진입차수가 0이라면 큐에 넣어준다
        for next in adj[now]:
            in_degree[next]-=1
            if in_degree[next]==0:
                q.append(next)
    print(' '.join(map(str,answer)))

 

 

 

회고

위상정렬(Topological Sorting)
1. 진입차수(In Degree)를 활용
2. 진입차수가 0인 노드를 제거하고, 이웃한 노드들의 관계를 제거한다 
-> 진입 차수가 0인 노드는 방문해야하는 노드