벨로그의 첫 이야기는 백준 알고리즘으로..
'선수과목'이라는 문제인데, 문제 이해부터 조금 어려울 수 있어서 해설부터 차근히 해보려 한다.
선수과목이라는 것은 어떤 과목을 수강하기 전 미리 수강해야 할 과목을 의미한다.
예를 들어 '자료구조'라는 과목을 수강하기 위해서는 '자료구조'라는 과목을 미리 수강해야 이해를 할 수 있음. 그러면 '자료구조'는 '알고리즘'의 선수과목이다.
문제는 읽었다는 가정 하에 예제를 봅시다.
예제 첫번째 줄에 있는 3과 2는 총 3개의 과목이 있고, 먼저 수강해야하는 2개의 조건이 있다는 뜻!
나머지 줄은 그 두가지 조건이다.
마찬가지로 6가지의 과목이 있고, 4가지의 조건이 있다는 뜻이다.
이제 문제를 이해했으니 풀어봅시다.
그 전에 이 문제는 '위상 정렬'이라는 것을 사용하는데(꼭 사용하지 않아도 된다고 함) 위상 정렬이 무엇인지 먼저 살펴보고 들어가보아요.
'위상 정렬'은 방향이 있는 그래프의 꼭짓점들을 순환없이 나열한 것을 의미한다.
위 예제를 위상 정렬로 표현하면 아래 그림과 같다.
1번 예제
2번 예제
위상 정렬을 살펴보기 전, 진입 차수와 진출 차수를 이해해야한다.
진입 차수는 해당 노드로 들어오는 간선을 의미하며
진출 차수는 해당 노드에서 나가는 간선을 의미한다.
위상 정렬 구현방법은 다음과 같다.
큐(Queue)를 이용하며
1. 진입 차수가 0인 모든 노드를 큐에 넣는다.
2. 큐에서 원소를 꺼낸다.
3. 해당 과목이 가리키고 있는 간선을 제거한다.
4. 진입 차수를 하나 빼준다.
5. 진입 차수가 0이 된 노드를 큐에 넣는다.
2~5를 큐가 빌 때까지 반복한다.
그러면 구현해보자.
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int,input().split())
indegree = [0] * (N+1) # 진입차수를 0으로 초기화
graph = [[] for i in range(N+1)] # 연결 리스트 초기화
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b) # a에다가 b를 넣어준다.
#1 2를 입력받으면 1번 노드에 연결된 간선인 2번 노드가 graph[1]에 저장된다.
indegree[b] += 1 # 진입 차수를 추가해준다.
answer = [1] * (N+1) # 정답이 입력될 리스트
def topology_sort(): # 위상정렬 구현
result = [] # 이 값은 위상 정렬 된 리스트
q = deque()
for i in range(1, N+1):
if indegree[i] == 0: # 진입차수가 0이면 큐에다 저장
q.append(i)
answer[i] = 1
for i in range(1, N+1):
now = q.popleft() # 선입선출
result.append(now)
for next in graph[now]:
indegree[next] -= 1 # 진입 차수를 하나 빼준다.
if indegree[next] == 0: # 진입차수가 0이 되면 큐에다 저장
q.append(next)
answer[next] = answer[now] + 1
print(*answer[1:])
topology_sort()내가 가장 많이 헤맸던 부분은 다음과 같다.
for next in graph[now]:
indegree[next] -= 1 # 진입 차수를 하나 빼준다.
if indegree[next] == 0: # 진입차수가 0이 되면 큐에다 저장
q.append(next)
answer[next] = answer[now] + 1이 부분이 이해하기 제일 어려웠다.
원래는 answer[next] += 1을 했는데 틀린답이 나왔다.
answer[now], 즉 다음 노드에 현재 노드의 값을 고려하고 1을 더해야 한다.
말로하니까 어려운데,
지금 예제로 보자면 1->2->3인 그래프에서
3과목의 학기를 계산하고자 한다면 3이라는 정답을 줘야 할 것이다.
하지만 3과목은 진입차수가 2인 1개밖에 없으므로 2라는 정답을 내게 될 것이다.
그렇기 때문에 현재 노드의 학기를 고려하고 정답을 줘야한다.
그리고 만약 간선 가중치가 있으면 아래와 같이 작성해야 함.
answer[next] = max(answer[next],answer[now]+1)
추가로 배운 것
print(*answer[1:]) 리스트를 펼쳐서 보여준다
