[BOJ] 1766번 - 문제집

최근 코테를 본 SW마에스트로에서 위상정렬 관련 문제가 나와서 알고리즘을 공부한 뒤 여러 문제들을 풀어봤다.

위상정렬에서는 충분한 조건이 주어지지 않으면 답이 여러가지가 나올 수가 있는데 이 과정에서 (항상 ~ 가 작은 순서로 한다) 등의

조건이 주어졌을 때 어떻게 해야할 지 잘 알려주는 문제이다

 

예를 들어 사람 3명이 옆의 조건을 만족하여 출력한다고 해보자. 2번이 1번보다 앞에 나와야 한다. 이 조건을 만족하도록 줄을 세울 때,

정답은 [ 2, 3, 1 ], [ 2, 1, 3 ], [ 3, 2, 1] 이런식으로 여러가지 답이 나올 수 있다. 하지만 여기서 위의 조건을 만족하고 가능한

나이가 많은 순서대로 출력한다고 생각하면 ( 가정 1 < 2 < 3 )

 

답: [ 3, 2, 1 ]  이 될것이다.

 

이와 비슷한 문제가 바로 이 문제이다.

www.acmicpc.net/problem/1766

1766번: 문제집

위상 정렬은 (topological sort) 라고 한다. 간단하게 위상정렬을 소개하도록 하겠다.

이 알고리즘은 해당 간선 간에 사이클이 없어야하고, 시작점이 없어서도 안된다. 

 

조건

3 번 문제를 풀기위해선 1번 문제를 풀어야 한다.

2 번 문제를 풀기위해선 1번 문제를 풀어야 한다.

2번 문제를 풀기 위해선 3번 문제를 풀어야한다.

4번 문제를 풀기 위해선 3번 문제를 풀어야한다.

 

초기 노드 정보

위의 그림으로 봤을 때 1번 문제를 가장 먼저 풀어야 할것을 알 수 있다.

degree[] 배열을 통해 각 노드가 화살표 즉 ,1번이 2,3 번을 가리킨다면 2,3번 노드는 degree[2] += 1 degree[3] += 1 이런식으로 초기 입력 값을 기준으로 화살표를 받은 노드들의 degree 값을 늘려주면 된다.

 

그렇다면 1번문제를 가장 먼저 풀어야 할 것을 알기 위해선

degree[i] 값이 0이어야한다. (이유: 먼저 풀어야할 것들이 없다는 것을 의미하기 때문이다.) 이뜻이 잘 모르겠다면 한 번 생각해봐야한다.

for i in range(len(degree)):
	if degree[i] == 0:
    	q.append(i)

 

1번 노드를 풀었다고 가정하면

 

1번노드를 풀었다 가정

1번 노드를 풀어야 2,3 번 노드를 풀 수 있으므로 degree[2], degree[3] 값을 각각 -1 해준다.

(1번 노드의 간선들을 파악하면서 -1 해주면 된다)

그런 뒤 만약 degree[] 값이 0이 된다면 해당 노드들을 q에다 넣어주면 된다.

 

3번 노드의 degree 값 0

3번 문제가 풀리고 3번 문제를 풀어야 풀 수 있는 문제들의 degree 값을 감소 시킨다. 그 뒤 degree 값이 0인 것들을 q에 넣자.

그렇다면 2,4 번이 q에 들어있게 될것이고 이들의 순서는 상관이 없다.

 

 

 

위와 같이 여러가지 경우의 수가 나올 수 있지만 본 문제에서는 한 가지 답만 나올 수 있다.

 

1. 문제집을 가능한 쉬운 순서대로 풀어야 한다. -> 이렇게 하기 위해서는 항상 queue에 들어 있는 값들 중 가장 작은 값이 나와야 한다.

 

2. 위 문제를 해결 하기 위한 자료구조를 생각한 뒤 위상정렬을 구현한다.

 

*  원래 썼던 자료구조 queue 에서 heapq를 쓰면 된다. 물론 그냥 queue에서 계속 탐색하며 가장 작은 값을 꺼내도 되지만,

*  그렇다면 아마 시간초과가 날것이다. heapq()는 push 와 pop 이 O(logN)이므로 이를 해결해 줄 수 있다.

 

알고보면 코드는 매우 간단한 로직 이였던 것 같다.

from sys import stdin
from heapq import heapify, heappop, heappush

std = stdin.readline

N, M = map(int, std().split())

book = [[] for i in range(N)]
degree = [0 for i in range(N)]

for i in range(M):
    a, b = map(int, std().split())
    book[a-1].append(b-1)
    degree[b-1] += 1
q, answer = [], []

for i in range(N):
    if degree[i] == 0:
        heappush(q, i)

while q:
    vertax = heappop(q)
    answer.append(vertax)
    for v in book[vertax]:
        degree[v] -= 1
        if degree[v] == 0:
            heappush(q, v)

for a in answer:
    print(a+1, end=" ")