BOJ(백준) 1766[문제집]

안녕하세요! 이번 포스트에서는 백준 1766번 문제 “문제집”을 함께 풀어보겠습니다. 이 문제는 문제를 풀기 위한 순서를 정하는 문제로, 위상 정렬을 활용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/1766

 

1. 문제 설명

“문제집” 문제는 문제를 풀기 위한 순서를 정하는 문제입니다. 문제를 풀기 위해 다음 규칙을 따라야 합니다:

 

1. 어떤 문제를 풀기 위해 다른 문제를 먼저 풀어야 하는 경우가 있습니다.

2. 이러한 문제들 간의 우선순위를 고려하여 모든 문제를 풀 수 있는 순서를 찾아야 합니다.

3. 여러 방법이 존재할 경우, 문제 번호가 더 작은 문제를 우선 풀어야 합니다.

 

2. 문제 접근법

이 문제를 해결하기 위해 위상 정렬(Topological Sorting)을 사용합니다. 핵심 아이디어는 각 문제를 풀기 위해 필요한 선행 문제의 개수를 관리하고, 이를 통해 문제를 풀어가는 순서를 정하는 것입니다. 접근 방법은 다음과 같습니다:

 

1) 초기값 설정

• 문제 수 N과 정보의 수 M을 입력받습니다.
• 인접 리스트를 초기화하여 각 문제의 선행 문제를 저장합니다.
• 각 문제의 진입차수를 저장할 리스트를 초기화합니다.

2) 위상 정렬 준비

• 진입차수가 0인 문제를 우선순위 큐(Priority Queue)에 추가합니다.

3) 위상 정렬 수행

• 큐가 빌 때까지 다음을 반복합니다:
• 큐에서 문제를 하나 꺼내어 결과 리스트에 추가합니다.
• 현재 문제와 연결된 모든 문제의 진입차수를 감소시키고, 진입차수가 0이 된 문제를 큐에 추가합니다.

4) 결과 출력

• 최종적으로 정렬된 결과 리스트를 출력합니다.

3. 정답 코드

from queue import PriorityQueue
import sys
input = sys.stdin.readline

N, M = map(int, input().split())    # N: 문제 수, M: 정보의 수 (간선의 수)
adj = [[] for _ in range(N+1)]      # 인접 리스트 초기화
inDegree = [-1] + [0] * N           # 각 노드의 진입차수를 저장할 리스트

for _ in range(M):
    a, b = map(int, input().split())    # a에서 b로 가는 간선
    adj[a].append(b)                    # 인접 리스트에 간선 추가
    inDegree[b] += 1                    # b의 진입차수 증가

pq = PriorityQueue()                    # 우선순위 큐 생성
for i in range(1, N+1):
    if inDegree[i] == 0:                # 진입차수가 0인 노드를 큐에 추가
        pq.put(i)

ans = []                                # 정렬된 결과를 저장할 리스트
while pq.qsize() > 0:                   # 큐가 빌 때까지 반복
    n = pq.get()  
    ans.append(n)                       # 결과 리스트에 추가
    for i in adj[n]:                    # 현재 노드와 연결된 모든 노드에 대해
        inDegree[i] -= 1                # 연결된 노드의 진입차수를 감소
        if inDegree[i] == 0:            # 진입차수가 0이 되면
            pq.put(i)                   # 큐에 추가

print(*ans)  # 결과 출력

 

4. 코드 설명

위 코드는 주어진 문제를 풀기 위한 순서를 위상 정렬을 사용하여 계산합니다. 각 단계별로 설명하면 다음과 같습니다:

 

1) 초기값 설정

• N과 M을 입력받고, 인접 리스트 adj와 진입차수 리스트 inDegree를 초기화합니다.
• for문을 통해 간선 정보를 입력받아 인접 리스트와 진입차수 리스트를 갱신합니다.

2) 위상 정렬 준비

• 진입차수가 0인 노드를 우선순위 큐에 추가합니다.

3) 위상 정렬 수행

• 큐에서 노드를 하나씩 꺼내어 결과 리스트 ans에 추가합니다.
• 현재 노드와 연결된 노드들의 진입차수를 감소시키고, 진입차수가 0이 되면 큐에 추가합니다.

4) 결과 출력

• 결과 리스트 ans를 출력합니다.

5. Github으로 확인

coTest/BOJ/BOJ01_10_05_2252.py at main · pcy4196/coTest