BOJ 1766 문제집 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

1번부터 N번까지 총 N개의 문제로 된 문제집을 풀려고 함.

문제 난이도는 순서대로. 1번문제가 가장 쉬운 문제, n번 문제가 가장 어려운 문제임.

먼저 풀면 좋은 문제가 있다는 걸 알게되어, 3가지 조건에 따라 문제풀이 진행.

1. n개의 문제는 모두 풀어야 함
2. 먼저 푸는 것이 좋은 문제는 반드시 먼저 풀어야 함(=선수 문제를 따라야 함)
3. 가능하면 쉬운 문제 부터 풀어야 함

e.g.) 4개의 문제, 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고 3번 문제는 1번 문제보다 먼저 푸는 것이 좋음.

만일 4-3-2-1 순서로 문제를 풀게되면, 조건 1,2는 만족하되, 조건 3은 만족못함.(3은 4보다 쉽기에 먼저 풀어야 함)

따라서 조건 3가지를 만족하려면 3-1-4-2가 된다.

• 입력

첫째 줄에 문제의 수 n(1≤n≤32000)와 선수 문제의 개수 m(1≤m≤100,000)

둘째 줄부터 m개 줄에 걸쳐 두 정수 a,b가 빈칸을 사이에 두고 주어짐.

이때 a는 b보다 먼저 푸는게 좋음.

항상 문제를 모두 풀 수 있는 경우에만 입력으로 주어짐.

• 출력

문제번호를 풀어야 하는 순서대로 빈칸을 두고 출력

두 번째 단계 (문제 핵심 파악)

먼저 풀어야 하는 문제는 마치 대학교 과목에서 선수과목이 있는 것처럼 무조건 선수관계를 지켜야 하는 것이다.

따라서, 선수관계가 있는 것을 그래프 로 떠올려보자.

3번 노드 → 1번 노드를 가리킴.

4번 노드 → 2번 노드를 가리킴.

이때 3번 노드랑 4번 노드 중에 더 쉬운 문제는 3번 노드임.

3번 노드를 풀고, 1번 노드와 4번 노드 중 먼저 풀어야 하는 건 1번 노드이기에 1번 노드를 푼다.

남은 건 2, 4번 노드이기에, 4번 노드를 풀고 2번 노드를 푼다.

사이클이 없으며 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 정렬 알고리즘인 위상 정렬

위상 정렬은 진입 차수, 진출 차수의 개념을 알아야 한다.

• 진입 차수(indegree): 특정 노드로 들어오는 간선 개수
• 진출 차수(outdegree): 특정 노드에서 나가는 간선 개수
  위상 정렬의 동작 과정

큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다

1. 진입차수가 0인 모든 노드를 큐에 넣는다
2. 큐가 빌 때까지 다음의 과정을 반복한다
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다

=> 결과 적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다

위상 정렬의 특징

• 위상 정렬은 DAG에 대해서만 수행할 수 있다
  • DAG (Direct Acyclic Graph): 순환하지 않는 방향 그래프
• 위상 정렬에서는 여러 가지 답이 존재할 수 있다
  • 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재한다
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다
  • 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못한다
• 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다

큐가 아니라 우선순위를 가진 큐인 heapq 를 이용해 위상정렬을 구현하겠음.

3번 노드를 방문 후 1, 4번 노드 중 우선순위가 높은 1번 노드를 먼저 풀어야 하기 때문이다.

파이썬의 heapq는 기본적으로 최소힙이기에 넣었다가 빼는 것만으로도 오름차순 정렬이 된다.

코드 작성

import heapq

n, m = map(int, input().split())

# 위상정렬 그래프
graph = [[] for _ in range(n + 1)]  # 1-based
# 진입 차수 리스트
indegree = [0 for _ in range(n + 1)]
# 우선순위 큐
que = []

# 선수문제
for _ in range(m):
    first, last = map(int, input().split())
    graph[first].append(last)
    indegree[last] += 1  # 진입차수 + 1 해준다


# 위상정렬
def topology_sort():
    # 정답 담을 리스트
    res = []
    # 1. 진입 차수가 0인 노드부터 큐에 삽입
    for i in range(1, n + 1):
        if indegree[i] == 0:
            heapq.heappush(que, i)
    # 2. 큐가 빌때까지 반복
    while que:
        # 큐에서 원소 꺼내기
        now = heapq.heappop(que)  # 오름차순 정렬 후 추출
        res.append(now)
        # 2-1. 해당 원소와 연결된 노드들의 진입차수에서 1을 뺀다.
        for j in graph[now]:
            indegree[j] -= 1
            # 2-2. 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[j] == 0:
                heapq.heappush(que, j)
    # 위상정렬 수행한 정답 출력
    for r in res:
        print(r, end=' ')


topology_sort()

느낀점

위상정렬이란것도 있구나.

처음에 먼저 풀어야 하는 문제를 자료구조화를 어떻게 할지 막막했는데, 그래프→위상정렬→우선순위 큐까지 도달하는 사고단계가 체계적이라서 풀기에 좋았다(?)

• 참고한 글
  위상 정렬 포스팅 설명 굿

[[알고리즘] 위상 정렬 (Topological Sorting)](https://velog.io/@kimdukbae/위상-정렬-Topological-Sorting)

문제 보고 고민 후 찾아본 포스팅 풀이 굿

[[백준] 1766번 문제집(feat. 위상 정렬, heapq)](https://mgyo.tistory.com/807)