안녕하세요, 이번 시간에는 위상 정렬을 다뤄보도록 하겠습니다.

 

위상 정렬은 방향이 있는 그래프에서 정점들을 정렬하는 방법입니다. 본격적인 정의를 배워보기 전에 실생활의 쉬운 예시를 들어 설명을 해보겠습니다.

 

대학교에서 선수 과목이 있는 과목들이 있습니다. 예를 들어 프로그래밍1 과목을 들어야 프로그래밍2 과목을 들을 수 있게 해놓은 것과 같은 상황을 말합니다.

 

이러한 관계들을 고려한 전체적인 과목 배치가 위와 같다고 해봅시다. 이 과목 배치 상에서 모든 과목을 수강하고 싶다고 하면 어떤 순서로 과목을 들어야할까요?

 

다양한 방법이 존재할 것입니다. 이산수학, 프로그래밍1, 프로그래밍2, 자료구조, 알고리즘, 객체지향 프로그래밍 순으로 들어도 되고, 이산수학을 최대한 미루고 미뤄 프로그래밍1, 프로그래밍2, 객체지향 프로그래밍, 자료구조, 이산수학, 알고리즘 순으로 들을 수도 있을 것입니다.

 

그러나 선수 과목을 지켜야하기 때문에 알고리즘을 먼저 듣고 이산수학을 그 다음에 듣는 것은 불가능할 것입니다.

 

이 때 과목을 정점으로 나타내고 과목의 선후 관계를 간선으로 나타낸 상황을 생각해봅시다.

 

그러면 이와 같은 모양이 나오게 됩니다. 이제 위상 정렬에 대해 이해할 수 있습니다. 위상 정렬은 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬입니다. 예를 들어 주어진 그래프를 보면 A에서 C로 가는 간선이 있으니 위상 정렬을 했을 때 A는 C보다 앞에 등장해야 합니다.

 

하나의 그래프에는 여러 개의 위상 정렬 결과가 있을 수 있습니다. 그림에서 ABCDEF, ACEDBF, BADCEF, BADFCE 등이 전부 올바른 위상 정렬입니다. 그러나 BFACED는 F가 D보다 먼저 나오기 때문에 잘못된 위상 정렬입니다.

 

만약 그래프 내에 사이클이 존재할 경우에는 올바른 위상 정렬이 존재할 수 없습니다. 주어진 그래프로 예를 들어보면, ABC 중에 그 어떤 것이 먼저 나오더라도 간선으로 주어진 정점 간 선후관계에 모순이 발생하기 때문입니다.

 

그렇기에 위상 정렬은 사이클이 존재하지 않는 방향 그래프에서만 잘 정의됩니다. 사이클이 존재하지 않는 방향 그래프를 DAG(Directed Acyclic Graph)라고 줄여서 부르기도 합니다.

 

위상 정렬에 대해 잘 이해했으니 주어진 그래프에서 위상 정렬을 어떻게 구현할지 생각해봅시다.

 

대충 눈으로 봤을 때 AGCDBEF 와 같은 순서가 보이긴 하지만 이걸 어떤 식으로 구할 수가 있는지 고민이 많이 됩니다.

우리가 위상 정렬을 눈으로 어떻게 알아냈는지 그 과정을 한 번 생각해보고, 코드로 옮겨낼 수 있도록 해보겠습니다.

 

만약 시간이 굉장히 촉박해 머릿속에 지식을 욱여놓고 있는 상황이라면 어쩔 수 없지만, 그렇지 않다면 머릿속으로 대강 떠오른 방식을 바로 코딩이 가능할 정도로 단계를 나누어 깔끔하게 정리를 해 pseudo code 비스무리 한 것을 만들어보는 것도 알고리즘 능력을 끌어올리기 위한 좋은 연습일 것입니다.

 

직접 한 번 해보셨다면 다음 장으로 넘어가봅시다.

 

다른걸 고민하지 말고 위상 정렬 상에서 제일 앞에 오는 원소로 가능한게 무엇일지 먼저 생각해보겠습니다.

 

제일 앞에 오기 위해서는 자신보다 앞에 위치해야 하는 정점이 하나도 없어야 할 것입니다. 이 말은 곧 자신에게 들어오는 간선이 없어야 함을 의미합니다. 예를 들어 그래프에서 A로부터 B로 가는 간선이 있습니다. 그렇기 때문에 B는 A가 나온 다음에야 등장할 수 있고, B는 제일 앞에 올 수 없습니다.

 

자신에게 들어오는 간선이 없다는 것을 indegree가 0이라고 표현을 할 수도 있습니다. indegree는 자신에게 들어오는 간선의 수를 의미합니다. indegree라는 표현이 낯설다면 빠르게 0x0F강 - 그래프에서 indegree와 outdegree를 찾아봅시다.

 

현재의 이 그래프에서는 A, G, C가 가능한 후보군임을 알 수 있습니다.

 

셋 중 어느 것이 제일 앞에 오더라도 전혀 상관이 없겠지만 임의로 A를 택하겠습니다. 위상 정렬에서의 첫 번째 정점은 A가 됩니다.

 

일단 A를 위상 정렬의 제일 앞에 위치시켰습니다. 이제 위상 정렬을 계속 이어나가기 위해 무엇을 해야할까요? A에서 다른 정점으로 나가는 간선을 생각해봅시다. 주어진 그래프에서는 A에서 B로 가는 간선만 존재합니다. A에서 B로 가는 간선은 A가 B보다 먼저 등장해야 한다는 제약 조건을 의미합니다. 그런데 이미 A는 다른 모든 정점들의 앞에 위치했기 때문에 이 제약 조건은 앞으로 신경쓰지 않더라도 자연스럽게 지켜질 것입니다. 이 말은 곧 A를 위상 정렬에 추가한 이후로는 A에서 다른 정점으로 나가는 간선이 의미가 없다는 의미입니다.

 

그렇기에 그냥 주어진 그래프에서 정점 A와 A에서 뻗어나가는 간선을 모두 지운 후, 위상 정렬을 이어나가면 됩니다.

 

정점 A가 제거된 후 B, C, D, E, F, G로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 C, G입니다. 어느 것을 택해도 상관없지만 임의로 C를 택하겠습니다. 위상 정렬에서의 두 번째 원소는 C가 됩니다.

 

마찬가지 논리로 정점 C와 C에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 C가 제거된 후 B, D, E, F, G로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 D, G입니다. C가 사라짐으로서 D가 추가되었네요. 어느 것을 택해도 상관없지만 임의로 D를 택하겠습니다. 위상 정렬에서의 세 번째 원소는 D가 됩니다.

 

정점 D와 D에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 D가 제거된 후에는 그래프가 분리되었습니다. 분리된 것을 신경쓰지 말고 과정을 이어가면 됩니다. B, E, F, G로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 B, G입니다. 어느 것을 택해도 상관없지만 임의로 G를 택하겠습니다. 위상 정렬에서의 네 번째 원소는 G가 됩니다.

 

정점 G와 G에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 G가 제거된 후 B, E, F로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 B, E입니다. 어느 것을 택해도 상관없지만 임의로 E를 택하겠습니다. 위상 정렬에서의 다섯 번째 원소는 E가 됩니다.

 

정점 E와 E에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 E가 제거된 후 B, F로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 B, F입니다. 어느 것을 택해도 상관없지만 임의로 B를 택하겠습니다. 위상 정렬에서의 여섯 번째 원소는 B가 됩니다.

 

정점 E와 E에서 뻗어나가는 간선을 모두 지웠습니다.

 

정점 E가 제거된 후 B, F로 이루어진 그래프에서 제일 앞에 위치할 수 있는 정점, 즉 자신에게 들어오는 간선이 없는 정점은 B, F입니다. 어느 것을 택해도 상관없지만 임의로 B를 택하겠습니다. 위상 정렬에서의 여섯 번째 원소는 B가 됩니다.

 

주어진 그래프에서의 위상 정렬이 완료되었습니다. 매 순간마다 들어오는 간선이 없는 정점을 제거함으로서 위상 정렬을 구현할 수 있습니다.

 

엄밀히 말해 우리는 사이클이 존재하지 않는 방향 그래프에서 해당 알고리즘이 늘 올바른 위상 정렬 결과를 내어준다는 점을 증명하지 않았습니다. 이 부분은 곧 사이클이 존재하지 않는 방향 그래프에서 indegree가 0인 정점이 반드시 존재하는지 여부를 확인함으로서 해결할 수 있게 됩니다. 이를 귀류법으로 증명할 수는 있지만 저희는 학부 알고리즘 과목을 수강하는 것이 아니라 코딩테스트에서 써먹을 수 있는 실전 알고리즘을 공부하는 것이기 때문에 생략하도록 하겠습니다.

 

그러니 사이클이 존재하지 않는 방향 그래프에서 해당 알고리즘이 늘 올바른 위상 정렬 결과를 내어준다고 믿고 계속 진행하겠습니다.

 

대충 방법은 알겠는데 이것을 코드로 어떻게 효율적으로 구현할 수 있을까요?

 

위의 구현에서 보면 간선과 정점을 지우고, indegree가 0인 정점을 찾고... 뭔가 많이 복잡해 보입니다.

 

곧이곧대로 구현을 해도 되지만 몇 가지 성질을 잘 집어낸다면 훨씬 더 간편하게, 그리고 더 효율적인 시간복잡도로 구현을 할 수 있게 됩니다.

 

첫 번째 성질은 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 갯수를 저장해두었다가 매번 뻗어나가는 정점들의 indegree 값만 1 감소시켜도 과정을 수행할 수 있다는 성질입니다.

 

두 번째 성질은 indegree가 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가하면 된다는 성질입니다. 목록은 큐로 관리할 계획입니다. 큐 대신 배열이나 스택 등을 활용해도 상관이 없습니다.

 

위상정렬 알고리즘 과정을 글로 정리해보면 위와 같습니다.

 

우선 과정을 눈으로 음미해보세요. 이후 이해를 돕기 위해 준비한 다음 슬라이드들을 확인해보세요.

 

우선 맨 처음 간선을 읽어들이면서 Indegree 배열을 다 채워줍니다. 그리고 큐는 비워둡니다.

 

Indegree 배열을 다 채운 후에는 Indegree가 0인 정점들을 큐에 넣습니다. 이 때 BFS나 DFS에서 하던 것과 같이 visited 방문 체크는 해줄 필요가 없습니다. 과정을 끝까지 보고 나면 이해가 되겠지만 앞으로는 Indegree가 0으로 바뀔 때 큐에 넣을 것이고 각 정점의 Indegree가 0으로 바뀌는 순간은 딱 1번씩 있기 때문입니다.

 

큐의 front에 있는 A를 가져와 위상 정렬 결과에 추가합니다. 정점 A를 "관념적으로" 지울 것이기 때문에 A로부터 연결된 정점 B의 Indegree가 1 감소합니다. 정점 B의 Indegree는 아직 0이 아니기 때문에 큐에 넣지 않습니다.

 

큐의 front에 있는 C를 가져와 위상 정렬 결과에 추가합니다. 정점 C를 "관념적으로" 지울 것이기 때문에 C로부터 연결된 정점 B, D의 Indegree가 1 감소합니다. 정점 B의 Indegree는 아직 0이 아니기 때문에 큐에 넣지 않습니다. 정점 D의 Indegree는 0이 되었기 때문에 큐에 추가해줍니다.

 

큐의 front에 있는 G를 가져와 위상 정렬 결과에 추가합니다. 정점 G를 "관념적으로" 지울 것이기 때문에 G로부터 연결된 정점 E의 Indegree가 1 감소합니다. 정점 E의 Indegree는 아직 0이 아니기 때문에 큐에 넣지 않습니다.

 

큐의 front에 있는 D를 가져와 위상 정렬 결과에 추가합니다. 정점 D를 "관념적으로" 지울 것이기 때문에 D로부터 연결된 정점 B, E의 Indegree가 1 감소합니다. 정점 B, E의 Indegree가 모두 0이 되었기 때문에 큐에 추가해줍니다.

 

큐의 front에 있는 B를 가져와 위상 정렬 결과에 추가합니다. 정점 B를 "관념적으로" 지울 것인데 B로부터 연결된 정점이 없으므로 Indegree의 값은 변화하지 않습니다.

 

큐의 front에 있는 E를 가져와 위상 정렬 결과에 추가합니다. 정점 E를 "관념적으로" 지울 것이기 때문에 G로부터 연결된 정점 F의 Indegree가 1 감소합니다. 정점 F의 Indegree는 0이기 때문에 큐에 추가해줍니다.

 

큐의 front에 있는 F를 가져와 위상 정렬 결과에 추가합니다. 정점 F를 "관념적으로" 지울 것인데 F로부터 연결된 정점이 없으므로 Indegree의 값은 변화하지 않습니다.

 

만약 그래프 내에 사이클이 존재할 경우 이 알고리즘은 어떻게 동작할까요?

 

그림을 재탕했는데요, 그림과 같이 ABC라는 사이클이 있을 경우 A, B, C는 어느 것도 Indegree가 0이 될 수 없습니다. A의 Indegree가 0이 되려면 B의 Indegree가 0이 되어 선택되어야 하는데, B의 Indegree가 0이 되려면 C의 Indegree가 0이 되어 선택되어야 하고, 정작 C의 Indegree가 0이 되려면 A의 Indegree가 0이 되어야 하기 때문에 A, B, C는 서로 물고 물려있기 때문입니다.

 

그렇기에 소개한 알고리즘으로 진행을 한다면 사이클에 포함된 정점은 절대 큐에 들어갈 수가 없게 됩니다. 이 말은 큐가 비어 알고리즘이 종료되었을 때 위상 정렬 결과에 모든 정점이 있지 않다는 얘기입니다. 그러므로 주어진 방향 그래프에 사이클이 있는지 혹은 없는지 여부를 모르더라도 일단 이 알고리즘을 돌리고 나면 위상 정렬 결과에 모든 정점이 포함되어있는지 여부를 확인함으로서 사이클이 있는지 없는지를 확인할 수 있고, 사이클이 없다면 위상 정렬의 결과까지 얻을 수 있습니다.

 

다음 장에는 구현 코드가 나와있습니다. 그런데 다음 장으로 넘기기 전에 직접 한번 구현을 해보시는 것을 추천드립니다.

 

구현 코드를 같이 봅시다. 우선 N개의 정점이 있고 번호는 1-indexed입니다. adj에는 0x0F강 - 그래프에서 배운 것과 같이 나에게서 뻗어나가는 정점의 목록이 저장되어 있습니다. 그리고 indeg에는 각 정점의 indegree가 저장되어 있습니다.

adj, indegree, n은 그래프 정보를 입력받을 때 미리 값을 다 넣어야 합니다. 미리 값을 어떻게 넣어둔다는 것인지 헷갈린다면 조금 있다가 실제 문제에 대한 풀이를 보면 도움이 될 것입니다.

 

코드의 흐름은 위에서 설명한 것과 판박이입니다. 이 때 C++11 이상이 지원될 경우 12, 13번 줄을 for(auto nxt : adj[cur])로 한 줄에 쓸 수 있습니다.

 

result에는 위상 정렬 결과가 저장되고 result의 길이가 n인지 여부를 통해 사이클이 있는지 판단할 수 있습니다.

 

이 알고리즘의 시간복잡도는 얼마일까요? 각 정점은 큐에 최대 1번 들어가고 indegree를 감소시키는 연산은 각 간선에 대해 딱 1번씩만 발생하기 때문에 시간복잡도는 $O(V+E)$입니다. 그래프에서의 BFS/DFS가 $O(V+E)$인 것과 비슷한 맥락입니다.

 

첫 번째 문제는 BOJ 2252번: 줄 세우기 입니다. 문제 상황을 살펴보면 그냥 대놓고 각 학생을 정점으로 뒀을 때의 그래프에서 위상 정렬을 수행하는 문제임을 알 수 있습니다. 전체 코드는 링크를 참조하시고, 입력을 어떻게 처리하는지만 한 번 짚고 가봅시다.

 

크게 어려울 것 없이 a에서 b로 가는 간선이 주어질 때, adj[a]에는 b를 추가하고 indeg[b]는 1 증가시켜주기만 하면 모든 준비가 끝납니다.

 

지금까지 배운 것을 잘 조합하면 충분히 혼자 힘으로 풀어낼 수 있으니 정답 코드를 보기 전에 직접 맞춰봅시다!!

연습 문제로는 적절한 아이디어로 그래프를 잘 구성해야 하는 BOJ 2623번: 음악프로그램 문제, 위상 정렬 그래프에서 DP를 해야 하는 BOJ 1005번: ACM Craft 문제를 두었습니다. 응용이 필요하기 때문에 많이 어려울 수 있습니다. 일단 시도를 해보시고, 해결법을 잘 모르겠고 다른 사람들의 풀이를 이해하는 것에도 어려움을 느낀다면 넘어가셔도 무방합니다.

 

이번 강의에서는 위상 정렬을 익혔습니다. 코딩테스트에서 그다지 많이 나오지 않는 유형이지만 구현이 그다지 어렵지 않은 편입니다. 문제에서 원소 간의 선후 관계가 주어지고 순서를 정해야 하는 상황이면 앞으로는 이번 강의에서 배운 위상 정렬을 떠올려 해결해봅시다. 고생 많으셨습니다!!

[실전 알고리즘] 0x10강 - 트리.pdf

1.40MB

 

이번 시간에는 트리를 다루어봅시다.

 

저희는 0x0D강에서 이진 검색 트리를 배우며 이미 "트리"라는 개념을 적당히 받아들였습니다.

 

당시에는 이런식으로 "꼭대기부터 아래까지 계층을 이루고 있고, 제일 꼭대기를 제외한 나머지 정점들은 위로 딱 1개와 연결이 되어있는 구조" 정도로만 받아들이고 넘어갔습니다.

 

그런데 이전 강의에서 배운 것도 있고 하니 잘 생각해보면 트리 또한 간선과 정점으로 이루어진 자료구조로, 그래프의 특별한 종류임을 알아차릴 수 있습니다.

 

이진 검색 트리때 소개했던 용어를 다시 한 번 정리하고 가겠습니다. 제일 꼭대기의 정점은 루트입니다.

 

간선으로 직접 연결된 상하 정점을 부모와 자식이라고 부릅니다.

 

자식이 없는 정점은 리프입니다. 그림에서는 총 4개의 리프가 있습니다.

 

그리고 루트와의 거리가 1인 정점은 Depth가 1인 것이고, 2인 정점은 Depth가 2입니다. Depth가 1인 정점은 3개, 2인 정점은 2개, 3인 정점은 3개가 존재합니다.

 

그렇다면 이번에는 트리를 수학적으로(정확히는 그래프이론적으로) 깔끔하게 정의해볼 시간입니다.

 

기본적으로 단순 그래프(=루프가 없고 서로 다른 두 점을 연결하는 간선이 최대 1개인 그래프) 상황을 가정합니다. 이 때 트리는 무방향이면서 사이클이 없는 연결 그래프로 정의됩니다.

 

뭔가 깔끔해보이긴 하면서도 좀 아리송하고... 왜 앞에서 소개한 트리 모양이 늘 "무방향이면서 사이클이 없는 연결 그래프"인지 잘 와닿지 않을 수 있습니다. 이해를 돕기 위해 첨언하자면 저희가 느낌적으로 알고 있는 "트리"라는 것이 연결 그래프이어야 함은 자명합니다. 또한 간선의 방향성은 없다고 칩시다. 그러면 남은 것이 "사이클이 없다"라는 부분일텐데, 사이클이 있을 경우 지금 그림에서 점선 모양의 간선이 추가되는 것 마냥 뭔가 트리 모양이 이상해져서 트리가 아니게 된다 정도로만 받아들이고 넘어가시면 되겠습니다.

 

굳이 증명이 필요하다면 계층 구조로서의 트리를 귀납적으로 정의한 후 귀납법을 통해 증명을 할 수는 있지만 불필요하다고 생각이 들어 생략하겠습니다.

 

트리의 수학적인 정의로부터 이 슬라이드에서 제시된 다양한 그래프들이 전부 트리임을 알 수 있습니다.

 

앞에서 이진 탐색 트리를 다룰 땐 계층적인 구조로서의 트리를 다루었지만 트리의 정의 상으로는 계층과 관계된 것이 없으며, 또 정점이 1개이고 간선이 없는 그래프도 트리임에 유의해야 합니다.

 

트리의 정의는 아래의 명제들과 동치입니다. 명제들은 모두 무방향 단순 그래프임을 가정합니다.

 

다양한 명제들이 있지만 모두를 외울 필요는 없고, 머릿속으로 한 번만 생각을 해보고 넘어가면 됩니다. 단 $V$개의 정점을 가진 트리는 $V-1$개의 간선을 가지고 있다는 성질과 임의의 두 점은 연결하는 simple path가 유일하다는 것은 기억해두는 것이 좋습니다.

 

트리에서는 임의의 노드를 루트로 만들 수 있습니다. 트리가 마치 구슬과 실로 연결되어 있다고 생각할 때 아무 구슬 하나를 잡고 위로 올린 상황이라고 생각해도 됩니다. 주어진 6개의 트리는 모두 같은 트리입니다.

 

트리에서 루트가 정해지고 나면 루트는 부모가 없고 나머지 모든 노드의 부모가 1개로 고정됩니다. 단, 루트가 달라지면 각 노드의 부모 또한 달라집니다. 예를 들어 1이 루트일 때는 2의 부모가 1이었지만 4가 루트일 땐 2의 부모가 4로 바뀌었습니다.

 

트리에서의 BFS와 DFS에 대해 알아보겠습니다.

 

기본적으로 트리는 그래프의 특별한 한 종류이기 때문에 이전 장에서 배운 BFS, DFS 알고리즘을 그대로 적용시킬 수 있습니다.

 

우선 BFS의 경우 임의의 시작점을 잡고 BFS를 돌리면 그 시작점을 루트로 정해서 트리를 재배치했을 때의 높이 순으로 방문을 하게 됩니다. 그림에서 1번 정점을 시작점으로 잡고 BFS를 돌리면 1, 2, 3, 4, 5, 6, 7, 8 순으로 방문을 하게 됩니다. 물론 큐에 무엇을 먼저 넣는지에 따라 (2, 3, 4), (5, 6), (7, 8) 사이에서는 순서가 바뀔 수 있습니다.

 

그런데 트리의 BFS에서는 살짝 독특한 점이 있는데, 루트가 아닌 아무 정점이나 잡고 생각을 해보면 인접한 정점들 중에 자신의 부모를 제외하고는 전부 자신의 자식이라 아직 방문하지 않았음이 보장됩니다.

 

그러니까 예를 들어 6번 정점을 볼 때를 생각해보면, 6번 정점은 4, 7, 8번 정점과 연결되어 있습니다. 4번 정점은 부모이고 또 6번 정점보다 위에 있으니 이미 이전에 방문했을 것이고 7, 8번 정점은 큐에 넣으면 됩니다.

 

즉 트리에서는 BFS의 과정 속에서 자신의 자식들을 전부 큐에 넣어주기만 하면 됩니다. 이 말은 곧 자신과 이웃한 정점들에 대해 부모만 빼고 나머지는 전부 큐에 넣으면 됨을 의미하고, 그렇기 때문에 vis 배열을 들고갈 필요가 없이 그냥 부모가 누구인지만 저장하고 있으면 됩니다.

 

부모의 정보는 BFS를 돌리면서 자식 정점을 큐에 집어넣을 때 채워줄 수 있습니다. 다음 장의 코드를 보면서 이해해봅시다.

 

일단 각 정점의 부모 번호를 저장할 p 배열을 만듭니다. 이 때 루트의 부모는 자연스럽게 0이 됩니다. 12번째 줄에서 nxt가 cur의 부모인지 확인해 만약 부모일 경우엔 건너뜁니다. 부모가 아니면 큐에 넣고 p[nxt] = cur로 만들어줍니다.

 

vis를 사용할 때와 코드의 흐름이 크게 달라지지는 않습니다. 당연히 시간복잡도도 $O(V+E)$ (인데 $E = V-1$이기에 그냥 $O(V)$가 됩니다.)로 동일합니다.

 

그러나 이렇게 p 배열을 사용함으로서 "root" 번호의 정점을 루트로 두었을 때 각 정점의 부모 정보를 BFS 한 번으로 알아낼 수 있게 됩니다. 부모 정보가 필요한 문제에서는 이를 활용할 수 있습니다.

 

p를 계산하는 것에서 추가로 depth를 전부 계산할 수도 있습니다. 자식의 depth는 부모의 depth + 1임을 이용하면 됩니다.

 

DFS에서도 시작점을 잡으면 그 시작점을 루트로 보낸 상황을 가정하는 것이 편합니다.

 

위와 같은 트리에서 DFS를 돌리면 1, 2, 5, 3, 4, 6, 7, 8 순으로 방문하게 됩니다. 일단 갈 수 있는 곳 까지 쭉쭉 들어가다가 더 이상 갈 수 없으면 돌아나와 다른 곳으로 간다고 생각하면 편합니다.

 

BFS와 비슷하게 자신과 연결된 정점들은 1개만 부모이고 나머지는 전부 자식이라는 성질을 이용해 vis 배열을 쓰는 대신 부모 배열과 depth 배열을 채우면서 처리가 가능합니다. 코드를 참고해보세요.

 

앞의 코드에서 queue만 stack으로 바꾸면 DFS로 처리가 가능합니다.

 

재귀를 사용하면 코드가 많이 깔끔해집니다.

 

그러나 전 슬라이드에서도 강조했지만 만약 스택 메모리가 1MB로 제한되어 있을 땐 $V$가 대략 3만 이상일 때 1-2-3-4-5-6-... 형태의 일자 트리 모양에서 스택 메모리 한계를 넘어설 수 있기 때문에 $V$가 클 떄에는 재귀로 DFS를 돌려서는 안됩니다.

 

단순 순회가 목적이라면 코드가 훨씬 간결해집니다. 굳이 p 배열을 둘 필요 없이 함수 인자로 parent를 넘겨주면 되고, 이렇게 코드를 만들 경우 출력을 제외하면 5줄, 출력을 포함하면 6줄에 DFS를 돌 수 있게 됩니다.

 

그렇기에 저는 재귀를 이용한 DFS를 굉장히 선호합니다.

 

그 다음으로 다룰 주제는 이진 트리에서의 순회입니다. 이진 트리는 0x0D강에서 이미 언급했지만 위의 그림과 같이 각 정점의 자식이 최대 2개인 트리를 말합니다.

 

지금까지 저희가 아는 순회 방식으로는 BFS와 DFS가 있지만 특별히 이진 트리에 대해 따로 이름이 붙은 순회들이 있습니다. 바로 레벨 순회와 전위/중위/후위 순회입니다. 이번 챕터에서는 4가지 순회를 익혀보고자 합니다.

 

그런데 그 전에 선행되어야 할 것이 있습니다. 바로 이진 트리를 코드에서 표현하는 방법입니다. 물론 이진 트리도 트리의 일종이자 더 나아가 그래프의 특수한 모습이기 때문에 그냥 adj에 넣어서 저장을 할 수는 있습니다. 그러나 이렇게 처리를 해버리면 왼쪽 자식과 오른쪽 자식을 구분할 수가 없게 됩니다.

 

그렇기에 이 대신에 left와 right를 저장하게끔 코드를 구성해두면 좋습니다. 예쁘게 짜려면 구조체를 만들고 left, right라는 이름의 구조체 변수를 두고 뭐 등등 방법이 있겠지만 이 곳은 실무가 아니라 코딩테스트이기 때문에 거창한 자료구조를 두는 대신 그냥 오른쪽의 코드처럼 lc, rc 배열을 만들면 됩니다. lc는 left child, rc는 right child의 약자입니다. left, right는 이미 namespace std에 존재하는 이름이기 때문에 사용을 피해야 합니다. 사용할 경우 "모호한 기호입니다(ambigious symbol)" 라는 컴파일 에러 메시지를 받게 됩니다. 사실 전 아예 더 줄여서 l 혹은 r로 쓰는 것을 선호하나 그래도 강의자료이니만큼 lc와 rc로 작성을 했습니다.

 

parents 배열은 사용하지 않더라도 소개할 4가지 순회를 진행할 때에는 문제가 없으나 parents 배열이 필요한 일이 있다면 만들어서 채워두어도 됩니다.

 

지금은 각 정점의 번호가 그냥 1번부터 차례대로 붙어있기 때문에 별다른 처리가 필요없지만 번호가 1에서 $10^9$ 사이의 수라던가 하는 식으로 된다면 1번부터 차례대로 새롭게 번호를 부여하고 val 배열과 같은 것을 사용해 재배치한 번호와 원래의 번호를 mapping 시키면 됩니다.

 

0이라는 값은 해당 자리가 비어있음을 의미합니다. 예를 들어 left[4] = 0이니 4의 left child가 없음을 의미합니다.

이 lc와 rc 배열의 값은 코딩테스트 문제에서 입력을 받으며 채워넣을 수 있는데 이 부분은 연습 문제의 풀이를 설명할 때 실제 문제를 예시로 들어 설명하기로 하고 일단 지금은 트리를 배열로 표현할 수 있다는 점만 설명하고 넘어가겠습니다.

 

레벨 순회(Level-order Traversal)은 이름 그래도 레벨, 즉 높이 순으로 방문하는 순회입니다. 위의 트리에서는 1, 2, 3, 4, 5, 6, 7, 8 순으로 방문하면 그것이 바로 레벨 순회가 됩니다.

 

우리는 이미 루트에서 BFS를 돌리면 자연스럽게 레벨 순회가 됨을 알고 있습니다. 그렇기에 레벨 순회는 크게 복잡하게 생각할 필요 없이 그냥 루트를 시작점으로 두고 BFS를 돌림으로서 구현이 가능합니다.

 

단, 현재는 lc, rc로 이진 트리를 표현하고 있는 상황이기에 이에 맞는 BFS 코드가 필요합니다. 구현은 그다지 어렵지 않은데, 이전 챕터에서 설명했듯 트리에서 BFS를 할 때에는 시작점이 루트라고 가정한 트리 모양에서 현재 보는 정점의 자식을 큐에 넣어주기만 하면 됩니다. 코드를 확인해보세요.

 

코드의 11, 12번째 줄에서 if(lc[cur] != 0), if(rc[cur] != 0)을 if(lc[cur]), if(rc[cur])로 조금 더 줄여서 작성할 수도 있습니다.

 

레벨 순회를 제외한 나머지 3개의 순회는 재귀적으로 정의가 됩니다. 조금 헷갈릴 수 있다만 일단 전위 순회의 과정을 이해하고 나면 나머지도 크게 어려움 없이 이해할 수 있을 것입니다.

 

일단 전위 순회부터 설명을 하겠습니다. 전위 순회는

1. 현재 정점을 방문한다.

2. 왼쪽 서브 트리를 전위 순회한다.

3. 오른쪽 서브 트리를 전위 순회한다.

로 이루어져 있습니다. 왼쪽/오른쪽 서브 트리라는 의미는 나의 왼쪽/오른쪽 자손들이 이루는 트리를 말합니다. 예를 들어 1의 왼쪽 서브 트리는 (2, 4, 5, 8)번 정점으로 이루어진 트리를 뜻하고 2의 오른쪽 서브트리는 (5, 8)번 정점으로 이루어진 트리를 뜻합니다.

 

재귀는 해도해도 늘 헷갈리는 존재임을 잘 알고 있습니다. 그렇지만 주어진 트리에서 전위 순회를 진행하는 과정을 보여드릴테니 당황하지 말고 같이 차근차근 과정을 따라가봅시다.

 

루트에서부터 전위 순회를 시작해봅시다. 일단 현재 정점을 방문하라고 하니 1을 방문합니다.

 

그 다음에는 왼쪽 서브 트리를 전위 순회해야 합니다. 1의 왼쪽 서브트리는 2를 루트로 하는 트리입니다.

 

2를 루트로 하는 트리로 넘어와 전위 순회를 다시 시작합시다. 현재 정점인 2를 방문합니다.

 

그 다음에는 왼쪽 서브 트리를 전위 순회해야 합니다. 2의 왼쪽 서브 트리는 4를 루트로 하는 트리입니다.

 

4를 루트로 하는 트리로 넘어와 전위 순회를 다시 시작합시다. 현재 정점인 4를 방문합니다.

 

그 다음으로 4가 루트인 트리에서 왼쪽 서브 트리의 전위 순회를 해야합니다. 그런데 4의 왼쪽 자식이 없기 때문에 4가 루트인 트리는 왼쪽 서브 트리를 가지고 있지 않습니다. 그러므로 아무 것도 하지 않고 넘어갑니다.

 

그 다음으로 4가 루트인 트리에서 오른쪽 서브 트리의 전위 순회를 해야합니다. 그런데 4의 오른쪽 자식이 없기 때문에 4가 루트인 트리는 오른쪽 서브 트리를 가지고 있지 않습니다. 그러므로 아무 것도 하지 않고 넘어갑니다.

 

여기서 알 수 있듯 왼쪽과 오른쪽 자식이 모두 존재하지 않는 정점, 즉 리프에서 전위 순회를 시작할 경우 자기 자신만을 방문하고 종료합니다. 앞으로는 리프에 진입한다면 굳이 한 단계 더 들어가지 않고 바로 순회 순서에 추가시킨 후 넘어가겠습니다.

 

4에서의 순회가 종료되었으니 돌아가 루트가 2인 트리에서 다음 단계인 오른쪽 서브 트리 전위 순회를 할 차례입니다. 4의 오른쪽 서브 트리는 5를 루트로 하는 트리입니다.

 

5를 루트로 하는 트리로 넘어와 전위 순회를 다시 시작합시다. 현재 정점인 5를 방문합니다.

 

그 다음으로 5가 루트인 트리에서 왼쪽 서브 트리의 전위 순회를 해야합니다. 그런데 5의 왼쪽 자식이 없기 때문에 5가 루트인 트리는 왼쪽 서브 트리를 가지고 있지 않습니다. 그러므로 아무 것도 하지 않고 넘어갑니다.

 

그 다음으로 5가 루트인 서브 트리에서 오른쪽 서브 트리의 전위 순회를 해야합니다. 5가 루트인 트리의 오른쪽 서브 트리는 8이 루트인 트리이고, 8은 왼쪽과 오른쪽 자식이 없기에 굳이 들어가지 않고 방문처리를 한 후 넘어가겠습니다.

 

5에서의 순회가 종료되었으니 돌아갑니다.

 

2에서의 순회도 종료되었으니 돌아갑니다. 이제 루트가 1인 트리에서 오른쪽 서브 트리의 전위 순회를 하면 됩니다. 지금까지의 예시로도 설명이 충분하다고 생각이 되어 과정을 더 기술하지는 않겠습니다.

 

오른쪽 서브 트리에서는 3, 6, 7 순으로 방문을 하게 되어 최종적으로 이 트리에서 전위 순회는 1, 2, 4, 5, 8, 3, 6, 7 순으로 이루어집니다.

 

눈치채셨는지 모르겠는데 전위 순회는 DFS와 방문 순서가 동일합니다. DFS가 일단 자기 자신을 방문한 후 첫번째 자식부터 들어가 거기에서 DFS를 다시 시작하는 구조이기 때문입니다.

 

그리고 구현은 재귀를 이용해 아주 간단하게 할 수 있습니다. 자기 자신을 출력한 후 왼쪽 자식과 오른쪽 자식 각각에 대해 존재할 경우 전위 순회를 하도록 구현하면 됩니다.

 

중위 순회는 왼쪽 서브 트리 -> 나 -> 오른쪽 서브 트리 순으로 처리하는 순회 방법입니다. 이미 전위 순회의 예시를 통해 재귀적으로 순회를 도는 것은 익숙하실테니 손으로 직접 순회 순서를 알아내보시는 것을 추천드립니다.

 

확인해보면 4, 2, 5, 8, 1, 6, 3, 7 순으로 방문이 이루어집니다. 이 순서는 트리의 모양에서 가장 왼쪽에 있는 것 부터 방문하는 순서입니다. 만약 트리가 이진 탐색 트리(=왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 트리)였다면 자연스럽게 크기 순으로 방문하게 됩니다.

 

마찬가지로 구현은 재귀를 이용해 간단하게 할 수 있습니다. 코드를 확인해보세요.

 

후위 순회는 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 나 순으로 처리하는 순회 방법입니다. 이것 또한 직접 한번 해보세요.

 

확인해보면 4, 8, 5, 2, 6, 7, 3, 1 순으로 방문이 이루어집니다. 전위 순회, 중위 순회와 달리 이 순서는 딱히 쉽게 설명할 방법이 없네요.

 

마찬가지로 구현은 재귀를 이용해 간단하게 할 수 있습니다. 코드를 확인해보세요.

 

서로 다른 트리라고 하더라도 순회 결과가 일치할 수 있습니다. 위의 두 투리는 레벨 순회 결과가 2 1 3으로 동일합니다. 다른 순회들에 대해서도 쉽게 이러한 예시들을 찾을 수 있습니다.

 

그렇다면 2개의 순회 결과가 주어졌을 때에는 그러한 트리가 유일할까요? 만약 중위 순회(Inorder)와 다른 순회가 주어진다면 유일하지만 중위 순회가 포함되어있지 않다면 유일하지 않습니다. 관련한 얘기는 엄청 중요한 내용이 아닌데 복잡하기까지 해서 하기에 링크를 남길테니 원하시면 들어가서 글을 읽어보세요. 글은 영문입니다.

 

BOJ 1991번: 트리 순회 문제를 같이 풀어봅시다. 이 문제에서는 주어진 트리의 전위, 중위, 후위 순회 결과를 출력하라고 합니다. 전위, 중위, 후위 순회를 하는 것 자체는 쉬운데 주어진 입력을 lc, rc에 넣는게 조금 어려울 수 있습니다.

 

한번 시도해보시고 코드를 확인해보세요. 입력을 처리하는 코드는 슬라이드에 나와있는 것과 같이 하면 됩니다. 알파벳을 다루는 것 보다 1, 2, 3, ... 을 다루는 것이 편하므로 이 부분에 대한 처리를 'A'-1 만큼 더하거나 뺌으로서 했습니다. 정답 코드를 확인해보세요.

 

이번 강의를 통해 여러분은 트리와 이진 트리의 표현법을 익혔고 트리에서 BFS/DFS를 할 수 있게 되었습니다. 그리고 이진 트리에서 4가지 순회를 할 수도 있습니다.

 

트리의 경우 깊게 들어가면 끝도 없이 어려워지지만 지금까지 배운 범위만으로는 마땅히 낼 문제가 많지는 않습니다. 문제집에 올려둔 2250번 문제를 풀어낼 수 있다면 코딩테스트에서 트리 파트는 크게 걱정하지 않으셔도 될 것입니다. 그러나 트리DP라는 유형의, 재귀적인 처리를 통해 트리에서 Dynamic Programming을 하는 알고리즘의 경우 강의에서는 다루지 않지만 충분히 공부해볼 가치가 있는 유형이니 시간이 남는다면 한 번 학습해보세요.

 

끝으로 연습 문제를 그룹 내 문제집에 두었으니 풀어보세요.

[실전 알고리즘] 0x0F강 - 그래프.pdf

3.16MB

안녕하세요, 오랜만입니다. 무려 5개월만이네요. 굉장히 늦어진 점 양해 부탁드립니다. 백수(진)이기 때문에 앞으로는 열심히 만들겠습니다.

 

이전 강좌들에는 ppt에 글씨가 굉장히 많았는데 이번에 형식을 싹 갈아엎었습니다. 완성을 한 후에 이전 강의들도 싹 다 리뉴얼을 할 계획입니다. 리뉴얼 전에 의견 들려주시면 적극 반영하도록 하겠습니다.

 

수학에서나 일상생활에서 그래프라는 말을 쓸 때는 이런 식으로 데이터를 시각화한 자료를 의미하는데, 자료구조에서 말하는 그래프는 이것과 전혀 상관이 없습니다.

 

자료구조에서의 그래프는 이 그림과 같이 점과 선으로 이루어진 자료구조를 의미합니다. 이 때 점을 정점(Node or Vertex)으로 부르고 선을 간선(Edge)라고 부릅니다. 또한 각 정점에 연결된 간선의 수를 차수(degree)라고 부릅니다.

 

그래프는 네비게이션에서 최단경로 찾기,검색엔진에서 랭킹 산정하기 등과 같이 객체 사이의 연결 관계를 설정해야 하는 상황에서 유용하게 활용할 수 있는 자료구조입니다.

 

그래프의 간선에 방향성이 없을 경우 무방향 그래프라고 부르고, 방향성이 있을 경우 방향 그래프라고 부릅니다. 간선에 방향성이 있다는 뜻은 간선이 마치 일방통행 도로와 같다고 생각하시면 됩니다.

 

방향 그래프의 경우 자신에게서 나가는 간선의 수를 outdegree, 들어오는 간선의 수를 indegree라고 부릅니다.

 

임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로를 사이클이라고 부릅니다. 그래프 내에 사이클이 존재하면 해당 그래프는 Cyclic Graph라고 부릅니다. 반대로 사이클이 존재하지 않는 그래프는 Acyclic Graph입니다. 오른쪽의 경우 얼핏 보면 왼쪽과 같이 사이클이 있는 것 처럼 보이나 간선의 방향성으로 인해 사이클에 존재하지 않음에 유의하세요.

 

또한 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프를 완전 그래프(Complete Graph)라고 부릅니다. 임의의 두 정점 사이에 경로가 존재하는 그래프는 연결 그래프(Connected Graph)라고 부릅니다.

 

그래프는 꼭 연결되어 있을 필요도 없고, 또 두 정점 사이의 간선이 반드시 1개 이하일 필요도, 또 간선이 반드시 서로 다른 두 정점을 연결해야 할 필요도 없습니다. 참고로 한 정점에서 시작해 같은 정점으로 들어오는 간선을 루프(loop)라고 부릅니다.

 

보통 문제에서는 필요에 따라 “그래프는 연결되어 있다/그래프는 연결그래프이다“, “두 정점 사이의 간선은 최대 1개 존재한다./같은 간선은 한 번만 주어진다“, “간선의 두 정점은 서로 다르다＂와 같이 조건을 엄밀하게 지정하는 경우가 많습니다. 그러나 이러한 말이 없다면 위와 같은 그래프의 형태에 대해서도 정답이 잘 나오도록 해야 합니다.

 

참고로 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프를 단순 그래프(Simple Graph)라고 부릅니다.

 

의외로 그래프라는 개념 자체는 배운 적이 있어서 알고 있지만 이것을 어떻게 코드로 표현해야 할지 모르는 프로그래머가 많습니다. 어떻게 나타내면 될지 같이 배워봅시다.

 

첫 번째 방법은 인접 행렬(Adjacency Matrix)을 이용하는 방식입니다. 편의상 각 정점에 번호가 붙어있다고 할 때, 연결된 두 정점에는 1을, 연결되지 않은 두 정점에는 0을 주면 그래프를 표현할 수 있습니다. 지금은 Undirected graph이기 때문에 자연스럽게 왼쪽 위와 오른쪽 아래를 연결하는 대각선에 대해 대칭인 형태가 나옵니다.

 

만약 Directed graph일 경우에는 이런 식으로 표현이 가능합니다. (2, 3)이 1이라는 의미는 2에서 3으로 가는 간선이 있다는 의미입니다.

 

엄밀히 말해서 1 혹은 0으로만 나타내는 이 표현법은 두 점을 잇는 간선이 여러 개일 경우 문제가 생길 수 있지만 일반적으로는 대부분의 문제에서 주어지는 그래프는 단순 그래프이므로 굳이 고려하지 않겠습니다.

 

인접 행렬로 그래프를 나타내면 정점이 V개이고 간선이 E개일 때 어떤 두 점이 연결되어 있는지를 $O(1)$에 알 수 있습니다. 가로와 세로가 각각 V인 2차원 배열이 필요하니 $O(V^2)$의 공간을 필요로 합니다. 그리고 어떤 점에 연결되어 있는 모든 정점의 목록을 알아내고 싶을 때에도 갯수와 무관하게 시간복잡도가 $O(V)$입니다.

 

구현은 굉장히 간단합니다. 일단 정점의 갯수 $V$와 간선의 갯수 $E$가 주어진 후 E줄에 걸쳐 간선이 주어진다고 해봅시다. 이러한 입력 형식은 앞으로 여러분이 풀게 될 대부분의 문제에서 사용하고 있는 입력 형식입니다. 이 때 간선을 입력받으면서 adj_matrix 변수에 1을 적절히 갱신해주기만 하면 됩니다. 간선이 단방향일 경우 adj_matrix[u][v]만 1로 만들고, 양방향일 경우에는 adj_matrix[u][v], adj_matrix[v][u]를 모두 1로 만들면 됩니다.

 

물론 matrix 크기는 정점의 번호가 1-indexed일 때 $V+1$ by $V+1$ 이상이어야 하고, 현재 코드에서는 10 by 10인데 필요에 따라서 늘리면 됩니다.

 

두 번째 방법은 인접 리스트(Adjacency List)를 이용하는 방식입니다. 이 방식은 인접 행렬과 비교했을 때 $V$가 크고 $E$가 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식이고, 코딩테스트에서는 인접 행렬보다 훨씬 많이 사용해야하는 방식이기 때문에 잘 익혀두시는게 좋습니다.

 

개념 자체는 크게 어렵지 않습니다. $V$개의 리스트를 만들어 각 리스트에 연결된 정점을 넣으면 됩니다.

 

만약 Directed Graph일 경우에는 마찬가지로 양쪽에 다 넣는 것이 아니라 한쪽에만 넣어주면 됩니다.

 

인접 리스트에서는 $O(V+E)$의 공간이 필요합니다. 일단 리스트가 V개 필요하고, 간선이 1개 있을 때 마다 Directed Graph일 때는 특정 리스트 1개에 원소가 1개 추가되고 Undirected Graph일 때는 특정 리스트 2개에 원소가 1개씩 추가됨을 생각하면 모든 리스트에서 원소의 갯수의 총합은 Directed Graph일 때 E개, Undirected Graph일 때 2E개이기 때문입니다.

 

그리고 특정 정점과 연결되어 있는 정점들을 순회하고 싶을 때에도 $O(V)$ 대신 딱 갯수만큼만 필요합니다. 예를 들어 3과 연결된 모든 정점을 출력하고 싶을 때 인접 행렬에서는 adj_matrix[3][1], adj_matrix[3][2], ... ,adj_matrix[3][5]를 보아야 했지만 여기서는 3번 리스트에서 원소 2개만 바로 확인하면 됩니다.

 

공간 복잡도가 $O(V+E)$라는 것은 $V$에 비해 $E$가 작을 때 굉장히 큰 이점을 줍니다. 예를 들어 $V$가 100,000이고 $E$가 200,000인 경우를 생각해봅시다. 이 경우 인접 행렬으로 그래프를 저장하려고 한다면 100,000 by 100,000 배열을 잡아야 하는데 이는 메모리 제한에 걸립니다. 그러나 인접 리스트 방식으로 저장하면 공간복잡도는 $O(V+E)$로 리스트 100,000개가 필요하고 모든 리스트에 저장되는 원소의 총 합이 200,000개 혹은 400,000개 저장되기 때문에 문제 없이 저장이 가능합니다.

 

문제는 이것을 어떻게 구현하는가인데, STL을 쓸 수 있는 환경이라고 할 경우 vector를 사용해서 구현하면 어렵지 않습니다. adj[i]는 정점 i와 연결된 정점들의 정보를 가지고 있습니다.

 

STL을 쓸 수 없는 환경일 때는 조금 까다롭습니다. 예를 들어 $V$가 100,000일 때 그래프가 단순그래프(루프가 존재하지 않고 두 정점을 잇는 간선이 1개 이하인 그래프)라면 각 정점의 degree는 최대 99,999입니다. 즉 한 리스트에 최대 99,999개의 정점이 들어갈 수 있는 것입니다. 하지만 그렇다고 해서 100,000개의 리스트를 전부 크기 99,999개의 배열로 잡아버리면 공간복잡도가 $O(V^2)$가 되어 인접 행렬과 다를 것이 없어집니다.

 

결국 STL 없이 동적 리스트를 사용할 수 있어야 하는데, 이를 위해 vector나 linked list class를 직접 만들어도 되지만 아무래도 실수할 여지가 많습니다. 대신 위의 코드와 같이 일단 간선의 목록을 입력받으며 차수를 세고, 이후 차수에 맞게 동적 배열을 잡는 식으로 구현을 하면 STL이 없어도 그다지 어렵지 않게 인접 리스트 방식을 구현할 수 있습니다. 이 코드는 방향그래프의 예시입니다.

 

adj[i]에 동적 할당을 할 때 deg[i]에 1을 더한 크기로 할당을 받는 까닭은 차수가 0일 때 new int[0]; 으로 0칸짜리 배열을 할당받는 것이 다소 꺼림직하게 느껴져서입니다. 1을 더하는 처리가 없어도 상관은 없습니다.

 

무방향 그래프일 때에는 맨 처음 입력받을 때 deg[edge[i][1]]도 1 증가시켜주고, adj에 추가도 양방향으로 해주는 것에 주의하면 구현은 크게 다르지 않습니다.

 

이제 여러가지 관점에서 두 표현 방법을 비교해봅시다.

 

우선 공간 복잡도는 인접 행렬의 경우 $O(V^2)$, 인접 리스트의 경우 $O(V+E)$입니다.

 

임의의 두 정점이 연결되어 있는지 확인하는 시간 복잡도의 경우, 인접 행렬은 그냥 adj_matrix[u][v]를 확인하면 되니 $O(1)$입니다. 인접 리스트에서는 한 정점에 대해 자신과 연결된 모든 정점을 확인해야 하는데, 둘 중에서 차수가 작은 것을 택해서 확인하는게 이득이므로 $O(min(deg(u), deg(v))$입니다.

 

한 정점이 연결된 모든 정점을 확인하는 시간 복잡도의 경우, 인접 행렬은 1번부터 $V$번까지에 대해 연결관계를 전부 확인해야 하므로 $O(V)$이지만 인접 리스트에서는 $O(deg(v))$ 입니다.

 

정리하면 인접 행렬은 두 점의 연결여부를 많이 확인할 때, 혹은 간선의 갯수가 $V^2$에 가까울 때 효율적입니다.

반대로 인접 리스트는 특정 정점에 연결된 모든 정점들을 자주 확인할 때, 혹은 간선의 갯수가 $V^2$보다 훨씬 적을 때 효율적입니다.

 

예를 들어 $V$가 100,000이고 $E$가 200,000일 경우에는 간선의 갯수 $E$가 $V^2$보다 훨씬 적으므로 인접 리스트를 사용하는 것이 효율적입니다. 반대로 $V$가 100이고 $E$가 7,000일 경우에는 인접 행렬을 사용하는 것이 효율적이긴 합니다. 그러나 일반적인 그래프 문제에서 "정점 u, v가 연결되어있는지를 반복적으로 확인해야 하는 경우"는 거의 없습니다.

 

또한 다음 챕터에서 배우게 될 BFS, DFS나 앞으로 배울 여러 경로 알고리즘들에서는 전부 특정 정점에 연결된 모든 정점을 확인하는 작업이 반복적으로 등장합니다.

 

그렇기 때문에 코딩테스트에서는 구현이 간단하다는 점 이외에는 인접 행렬을 사용해서 얻는 이점이 없다고 볼 수 있으며 99% 이상의 경우 인접 리스트로 그래프를 나타낸다고 생각하시면 됩니다.

 

특이하게 입력 자체가 인접 행렬 느낌으로 주어지거나 $V$가 많이 작아 구현의 편의를 위해 인접 행렬로 푸는 경우가 가끔씩 있지만 기본적으로는 인접 리스트만 다룰 수 있어도 코딩테스트에서 불편함이 없습니다.

 

뜬금없이 BFS가 튀어나왔습니다. BFS는 한참 전에 했던 것 같은데.. 왜 그래프에서 BFS가 나오는걸까요?

 

지금은 기억이 잘 안나시겠지만 0x05강에서 BFS를 처음 소개할 때 이렇게 표현했습니다. “BFS는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘입니다. 원래 BFS와 DFS는 그래프 자료구조에서 모든 정점을 순회하기 위한 알고리즘으로, 다차원 배열이 그래프 자료구조의 특수한 형태이기 때문에 다차원 배열에서도 BFS, DFS를 사용할 수 있는 것입니다.”

 

즉, 지금까지는 다차원 배열에서 BFS와 DFS를 사용했지만 사실 BFS와 DFS는 그래프 자료구조에서 모든 정점을 순회할 때 쓰이는 알고리즘입니다. 예를 들어 왼쪽의 2차원 맵을 사실 오른쪽의 그래프와 같이 생각해도 상관이 없습니다. 파랑이 갈 수 있는 칸이고 빨강이 갈 수 없는 칸입니다.

 

이미 2차원 배열에서의 BFS에는 충분히 익숙하실테니 그래프에서의 BFS도 쉽게 이해하실 수 있습니다. 같이 한 번 과정을 따라가보겠습니다.

 

 

우선 방법을 글로 나타내면 이렇습니다. 2차원 배열에서 BFS를 할 때와 크게 다르지 않습니다.

 

2차원 배열에서는 상하좌우로 인접한 칸에 대해 살펴봤다면 그래프에서는 연결된 모든 정점을 살펴본다는 점만 차이가 있습니다. 만약 그래프가 Directed Graph일 때에는 자신으로부터 나가는 간선으로 연결된 점들만 살펴보면 됩니다.

인접 행렬일 경우에는 3번 과정이 $O(V)$가 필요하고 3번 과정을 $V$번에 걸쳐 진행하므로 $O(V^2)$임을 받아들일 수 있을 것입니다.

 

그러나 인접 리스트에서 시간복잡도가 $O(V+E)$인게 조금 헷갈릴 수 있는데, 모든 정점들에 대해 그 정점과 연결된 모든 정점을 살펴보는 과정의 총 합이 Directed Graph에서 $E$, Undirected Graph에서 $2E$가 필요해서 그런 것입니다. 잘 이해가 안간다면 다음 슬라이드의 그림을 참고해주세요.

 

“모든 정점들에 대해 그 정점과 연결된 모든 정점을 살펴보는 과정의 총 합이 Undirected Graph에서 $2E$이다” 라는 말을 그림으로 이해시켜드리겠습니다. 현재 간선은 8개입니다.

 

7개의 각 그래프는 1번부터 7번까지의 정점이 자신과 연결된 정점을 탐색하는 상황을 나타낸 것입니다.

 

그림을 살펴보면 각 간선은 2번씩 등장합니다. 이는 논리적으로 생각해도 당연한게 u와 v를 연결하는 간선은 u와 연결된 모든 정점을 살펴볼 때, 그리고 v와 연결된 간선을 살펴볼 때 한 번씩 등장하겠죠. 그리고 만약 directed graph였다면 u에서 v로 가는 간선은 u와 연결된 모든 정점을 살펴볼 때에만 등장하게 됩니다.

 

그러므로 앞에서 설명한 2번 “모든 정점들에 대해 그 정점과 연결된 모든 정점을 살펴보는 과정”은 $2E$ 혹은 $E$번의 탐색을 필요로 하고, 이로 인해 시간복잡도가 $O(V+E)$ 이 됩니다.

 

다시 한 번 강조하지만 시간복잡도에 $E$가 포함된다는 것을 유념하셔야 합니다.

 

예를 들어 V가 2,000인 완전그래프(=모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프)에서 간선은 대략 2,000,000개인데 여기서 BFS를 1000번 돌리는 풀이를 생각한 경우 이것의 시간복잡도는 $O(1000V)$가 아니라 $O(1000(V+E))$이고 시간초과가 발생하게 됩니다.

 

그러면 BFS를 같이 한번 해봅시다.

 

이제 직접 BFS를 해보겠습니다. 시작 정점은 어느 것이어도 상관이 없지만 임의로 1번부터 시작하겠습니다.

 

일단 1번 정점을 큐에 넣고 방문했다는 표시를 남깁니다.

 

큐가 비어있지 않으므로 큐의 front인 1번 정점을 꺼냅니다.

 

1번 정점과 이웃한 2, 3, 4번 정점은 모두 아직 방문하지 않은 정점이므로 방문했다는 표시를 남기고 큐에 넣습니다.

 

큐가 비어있지 않으므로 큐의 front인 2번 정점을 꺼냅니다. 2번 정점과 이웃한 1번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

큐가 비어있지 않으므로 큐의 front인 3번 정점을 꺼냅니다.

 

3번 정점과 이웃한 정점은 1, 4, 5번 정점입니다. 이 중에서 5번 정점만 유일하게 방문하지 않은 정점이므로 방문했다는 표시를 남기고 큐에 넣습니다.

 

큐가 비어있지 않으므로 큐의 front인 4번 정점을 꺼냅니다. 4번 정점과 이웃한 1, 3번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

큐가 비어있지 않으므로 큐의 front인 5번 정점을 꺼냅니다.

 

5번 정점과 이웃한 3, 6, 7번 정점 중에서 3번 정점은 이미 방문한 정점입니다. 6, 7번 정점은 아직 방문하지 않은 정점이므로 방문했다는 표시를 남기고 큐에 넣습니다.

 

큐가 비어있지 않으므로 큐의 front인 6번 정점을 꺼냅니다. 6번 정점과 이웃한 5, 7번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

큐가 비어있지 않으므로 큐의 front인 7번 정점을 꺼냅니다. 7번 정점과 이웃한 5, 6번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

큐가 비었으므로 과정이 종료됩니다.

 

그래프의 BFS에서도 2차원 배열의 BFS와 동일하게 시작점에서 다른 모든 점으로의 최단 경로를 찾을 때 이용할 수 있습니다.

 

BFS의 과정 속에서 현재 보는 정점으로부터 추가되는 인접한 정점은 시작점으로부터 1만큼 더 떨어져 있습니다.

 

즉, 모든 간선의 길이가 동일한 상황에서 두 지점 사이의 거리를 찾는 문제는 BFS로 해결이 가능합니다. 그러나 만약 모든 간선의 길이가 다르다면 이 문제는 Floyd, Dijkstra, Bellman Ford와 같은 다른 알고리즘을 사용해야되고 이러한 알고리즘은 몇 강 후에 배우게 될 것입니다.

 

이 예시 코드는 순회만 하는 코드입니다. 인접 리스트 방식으로 그래프가 저장되어 있고 정점은 1번부터 순차적으로 매겨져있다고 가정합니다.

 

이미 2차원 배열에서 BFS를 많이 해보았기 때문에 코드의 흐름이 크게 낯설지 않을 것입니다.

 

만약 C++11이 지원되는 환경이라면 for문에서 i를 0부터 adj[cur].size까지 증가시키는 대신 for(auto nxt : adj[cur]) 로 타이핑을 덜 낭비하고 구현할 수 있습니다.

 

만약 STL이 지원되지 않는 환경이라면 큐를 별도로 구현하고 i를 adj[cur].size 대신 deg[cur]까지 증가시키면 될 것입니다.

 

큐에 넣은 직후에 vis의 값을 true로 갱신해줘야 함에 유의해야 합니다.

 

인접 행렬로 BFS를 구현하면 시간복잡도가 $O(V^2)$으로 더 비효율적이라 비추천하지만, 굳이 필요하다면 for문 부분을 for(int nxt = 1; nxt <= V; nxt++)으로 변경하고 adj_matrix[cur][nxt]가 1일 때만 아래의 과정을 진행하도록 코드를 수정하면 됩니다.

 

 

이 예시 코드는 1번 정점과의 거리를 구하는 코드입니다. 두 정점 사이의 거리는 거쳐야 하는 간선의 최소 갯수로 정의하면 됩니다.

 

dist를 먼저 -1로 초기화시키는 것을 빼먹으면 안됩니다.

 

0으로 초기화시키고 자기 자신과의 거리를 1로 두어도(즉 dist[1] = 1로 두어도) 상관은 없습니다.

맨 처음 for문으로 dist를 초기화시키는 과정을 fill(dist+1, dist+10, -1); 로 나타내면 타이핑을 절약할 수 있습니다.

 

예시 코드 1은 연결 그래프가 아닐 경우 모든 정점을 방문할 수 없습니다. 예를 들어 위와 같은 그래프라면 예시 코드 1이 5번과 6번 정점을 순회하지 못하게 될 것입니다. 이를 해결하기 위해 1번만을 시작 정점으로 잡는 대신 모든 아직 방문하지 않는 정점을 시작 정점으로 잡게끔 코드를 변형하면 됩니다. 코드 예시를 확인해보세요.

 

 

그 다음은 DFS입니다. 큐로 처리하던 것을 스택으로 한다는 점만 다르고 전반적인 흐름은 BFS와 동일하기 때문에 굳이 과정에 대한 설명을 다시 하지는 않겠습니다. 예시를 같이 봅시다.

 

DFS도 같이 해봅시다. 시작 정점은 어느 것이어도 상관이 없지만 임의로 1번부터 시작하겠습니다.

 

일단 1번 정점을 스택에 넣고 방문했다는 표시를 남깁니다.

 

스택가 비어있지 않으므로 스택의 top인 1번 정점을 꺼냅니다.

 

1번 정점과 이웃한 2, 3, 4번 정점은 모두 아직 방문하지 않은 정점이므로 방문했다는 표시를 남기고 스택에 넣습니다.

 

스택이 비어있지 않으므로 스택의 top인 4번 정점을 꺼냅니다. 4번 정점과 이웃한 1, 3번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

스택이 비어있지 않으므로 스택의 top인 4번 정점을 꺼냅니다. 4번 정점과 이웃한 1, 3번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

스택이 비어있지 않으므로 스택의 top인 3번 정점을 꺼냅니다.

 

3번 정점과 이웃한 정점은 1, 4, 5번 정점입니다. 이 중에서 5번 정점만 유일하게 방문하지 않은 정점이므로 방문했다는 표시를 남기고 스택에 넣습니다.

 

스택이 비어있지 않으므로 스택의 top인 5번 정점을 꺼냅니다.

 

5번 정점과 이웃한 3, 6, 7번 정점 중에서 3번 정점은 이미 방문한 정점입니다. 6, 7번 정점은 아직 방문하지 않은 정점이므로 방문했다는 표시를 남기고 스택에 넣습니다.

 

스택이 비어있지 않으므로 스택의 top인 7번 정점을 꺼냅니다. 7번 정점과 이웃한 4, 6번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

스택이 비어있지 않으므로 스택의 top인 6번 정점을 꺼냅니다. 6번 정점과 이웃한 5, 7번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

스택이 비어있지 않으므로 스택의 top인 2번 정점을 꺼냅니다. 2번 정점과 이웃한 1번 정점은 이미 방문한 정점이므로 넘어갑니다.

 

스택이 비었으므로 DFS가 종료됩니다.

 

2차원 배열의 DFS와 마찬가지로 그래프의 DFS는 시작점으로부터의 거리를 알아낼 때 사용할 수 없습니다.

 

위와 같은 그래프에서 DFS를 돌리면 BFS와는 다르게 DFS의 과정 속에서 현재 보는 정점으로부터 추가되는 인접한 정점은 시작점으로부터 1만큼 더 떨어져 있다는 성질이 만족되지 않음을 알 수 있습니다.

 

이 예시 코드는 순회만 하는 코드입니다. 인접 리스트 방식으로 그래프가 저장되어 있고 정점은 1번부터 순차적으로 매겨져있다고 가정합니다.

 

큐 대신 스택을 사용했다는 것만 BFS와 차이가 있고 코드의 흐름은 동일합니다.

 

DFS는 재귀를 이용해서도 구현할 수 있습니다. 재귀적으로 함수를 호출하는 것 자체가 자연스럽게 스택을 이용하는 모양새가 되기 때문에 별도로 스택을 선언할 필요가 없어집니다.

 

재귀적으로 구현을 한다면 함수 인자로 현재 노드의 번호를 입력받게 되는데, 이 때 만약 1번 노드부터 시작하고자 한다면 vis[1]을 true로 만들어놓고 dfs(1)을 호출해야함에 주의해야합니다.

 

재귀로 구현을 하게 되면 코드가 알아보기 쉽고 타이핑도 덜 낭비할 수 있습니다. 그러나 스택 메모리의 제한이 작은 경우 재귀 구현에는 아주 큰 문제가 있는데, 재귀적으로 들어갈 때 마다 메모리 중 스택 영역에 계속 데이터가 쌓이게 된다는 점입니다.

 

예를 들어 그래프가 1 -> 2 -> 3 -> ... -> 100,000 과 같이 일자로 생겨있다고 하면 dfs 재귀 구현에서는 dfs(1) -> dfs(2) -> dfs(3) -> ... -> dfs(100,000)으로 호출이 진행될 것입니다. 이렇게 되면 스택 영역에 최대 함수 100,000개의 데이터가 쌓이게 됩니다.

 

원래라면 이것은 256MB나 512MB 제한에 전혀 걸리지 않습니다. 그러나 온라인 저지중에 스택 영역의 메모리를 1MB로 제한하는 저지가 있고 대표적으로 현재(=2019년 12월 기준) SW Expert Academy가 그렇습니다. 스택 메모리가 1MB로 제한될 경우 깊이 10만의 재귀 함수는 반드시 스택 메모리 크기 제한을 넘기게 되고, 이로 인해 런타임에러가 발생합니다. 아마 삼성에서 주관하는 코딩테스트에서도 동일한 플랫폼을 사용할 것이기에 마찬가지로 스택 메모리 제한이 1MB일 것입니다.

 

왜 굳이 스택 영역의 메모리를 1MB로 제한하는지는 모르겠지만 어쨌든 스택 메모리의 제한이 1MB인 곳에서는 재귀 대신 그냥 stack STL 혹은 직접 구현한 stack을 이용해 DFS를 도는 것이 바람직합니다.

참고로 백준 온라인 저지에서는 별도의 스택 메모리 제한은 존재하지 않아 재귀적으로 구현해도 상관없습니다.

 

이처럼 DFS를 구현하는 방식을 크게 재귀를 사용하는 방식과 재귀를 사용하지 않는 방식으로 나눌 수 있습니다.

 

두 방식 모두 특정 정점으로 시작해 도달할 수 있는 모든 정점을 순회하는 역할을 잘 수행합니다.

 

그러나 둘은 실제 동작에서 약간의 차이가 있는데, 위의 예시를 한번 봅시다.

 

위와 같은 그래프에서 재귀적인 방식으로 DFS를 돌면 1 2 4 3 순으로 방문을 합니다. 그러나 비재귀적인 방식으로 DFS를 돌면 맨 처음 1번 정점을 스택에서 뽑았을 때 이웃한 2, 3, 4번 정점에 모두 방문했다는 기록을 남겨놓고 다음 정점으로 넘어가기 때문에 1 2 3 4 순으로 방문을 하게 됩니다.

 

즉 재귀적인 방식과 비재귀적인 방식은 방문했다는 기록을 언제 남기냐에 대한 차이가 있습니다.

 

엄밀히 말해 우리가 관념적으로 생각하는 DFS는 비재귀 DFS가 동작하는 방식과는 차이가 있고 재귀 DFS가 동작하는 방식과 일치합니다. 미로를 가지고 비유하면 미로를 탈출하기 위해 갈림길에서 갈 수 있는 아무 방이나 찍어 쭉쭉 들어가다가 더 이상 갈 수 없으면 되돌아오는 것이 관념적으로 생각하는 DFS이자 재귀 DFS이지 갈림길에서 다른 방들에는 마크를 두고 한 방만 정해서 들어가는 방식은 아니기 때문입니다.

 

다시 한 번 강조하면 비재귀 DFS는 순회를 잘 수행하지만 우리가 관념적으로 생각하는 DFS와 세부 동작이 다릅니다. 그래서 단순히 Flood Fill 내지는 순회를 하는 것이 아니라 DFS의 고유한 성질을 사용해 문제를 해결해야 하는 상황일 경우 앞에서 소개한 비재귀 코드를 이용하면 안됩니다.

 

그러나 비재귀 또한 우리가 관념적으로 생각하는 DFS와 동일하게 동작하도록 바꿀 수 있습니다.

 

이전 비재귀 DFS 코드에서는 스택에 넣은 직후에 방문 여부를 true로 만들어 스택에 각 정점이 무조건 1번씩만 들어가도록 만들었습니다. 이를 stack에서 값을 뽑은 후에 방문 여부를 true로 만들도록 수정하면 우리가 관념적으로 생각하는 DFS와 동작이 일치하게 됩니다.

 

스택 자체에는 각 정점이 무조건 1번씩 들어가지는 않고 여러 번 들어갈 수도 있지만 09번 줄의 처리로 인해 연결된 정점을 훑는 작업을 각 정점마다 1번씩 하기 때문에 시간복잡도는 동일하게 $O(V+E)$입니다.

 

만약 실수로 09번 줄을 빼먹는다면 코드의 시간복잡도가 굉장히 안좋아지거나 무한루프에 빠질 수 있게 됩니다. 이런 경우 제출했을 때 시간 초과 혹은 스택에 push가 계속 일어남으로서 메모리 초과가 발생하게 됩니다.

 

혹시 이전 슬라이드와 이번 슬라이드에서 다루는 내용이 잘 이해가지 않는다면 그냥 본인에게 편한 비재귀 방식 하나만을 익혀두고 넘어가셔도 상관없습니다. DFS의 고유한 성질을 사용해서 해결해야 하는 문제는 cycle detection, scc, bcc, Eulerian trail 등과 같이 코딩테스트에서는 나올 확률이 0에 수렴하는 어려운 문제들이기 때문입니다.

 

어차피 코딩테스트 레벨에서는 그래프에서의 flood fill 정도만을 요구할 것이기 때문에 DFS, BFS를 가리지 않고 순회만 할 수 있으면 크게 문제가 없을 것입니다.

 

참고로 개인적으로는 코드가 짧다는 이유로 그래프에서 재귀적으로 DFS를 하는 것을 선호합니다.

 

DFS도 마찬가지로 아직 방문하지 않은 시작점에서 DFS를 돌리는 방식으로 연결 그래프가 아닐 때 순회를 처리할 수 있습니다.

 

마지막으로 연습 문제 2개를 살펴보겠습니다. 첫 번째 문제는 BOJ 11724번: 연결 요소의 갯수 입니다. 문제를 확인해보시면 알겠지만 Undirected Graph에서 연결 요소의 갯수를 구하는 문제입니다.

 

그래프가 연결 그래프가 아닐 때 순회하던 방식을 조금 응용해 새로운 시작점이 나올 때 마다 카운트를 증가시키는 방식으로 해결이 가능합니다. (정답 코드)

 

두 번째 문제는 BOJ 1260번: DFS와 BFS 입니다. 이 문제에서는 DFS와 BFS를 실제로 돌도록 요구합니다.

 

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 조건을 맞추기 위해 adj를 정렬하는 과정이 추가로 들어가있습니다. 이외에는 위에서 썼던 코드를 그대로 활용하면 됩니다. 비재귀 버전과 재귀 버전의 코드를 다 두었으니 정답 코드를 확인해보시고 또 직접 구현해보세요. (정답 코드 - 비재귀, 정답 코드 - 재귀)

 

이번 강의를 통해 여러분은 그래프의 표현법을 익혔고 그래프에서 BFS/DFS를 할 수 있게 되었습니다.

 

엄밀히 말해 2차원 배열에서 DFS 혹은 BFS를 하도록 요구하는 문제는 끝도 없이 쌓여있지만 그래프에서 단순하게 DFS, BFS만을 하도록 요구하는 문제는 별로 없습니다. 다만 앞으로 Floyd, Dijkstra, Bellman-Ford와 같은 알고리즘을 익힐 때 그래프를 알고 있어야 하기 때문에 이렇게 한 강의를 할애해 그래프를 설명했던 것입니다.

 

보통 그래프와 관련해 BCC, SCC, DFS Tree 정도는 학교 수업시간에 다루는 경우도 있습니다만 코딩테스트에 나오기에는 고난이도의 문제라고 생각이 들어 적지 않았습니다. 위상 정렬과 최소 신장 트리(Minimum Spanning Tree)는 다다음 강에서 소개를 할 계획입니다.

 

끝으로 연습 문제를 그룹 내 문제집에 두었으니 풀어보세요.