위상정렬(topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다.
| 기능 | 특징 | 시간 복잡도(V: 노드 수, E: 에지 수) |
| 노드 간의 순서를 결정함. | 사이클이 없어야 함. | O(V+E) |
위상 정렬에서는 항상 유일한 값으로 정렬되지 않습니다. 또 사이클이 존재하면 노드 간의 순서를 명확히 정의할 수 없어 위상정렬을 적용할 수 없습니다. 아래 구체적인 시나리오를 통해서 단계별로 알아봅시다.
위상 정렬의 원리
1. 그래프에서 진입차수(in-degree) 을 저장합니다.
진입차수는 자기 자신을 가리키는 에지의 개수입니다. 1 에서 2, 3 을 가리키고 있으므로 D[2], D[3] 을 각각 1을 증가하는 식으로 계산하면 진입 차수 배열 D[N] 을 구할 수 있습니다.
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장합니다. 그 후에 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺍니다.
3. 계속해서 다음 진입 차수가 0인 노드를 선택하고 같은 동작을 반복합니다.
처음 진입 차수가 0인 노드 1을 선택하고 나서 위 그림에서는 다음 진입 차수가 0인 노드 2, 3 중에서 2을 선택했습니다.
하지만 이 때 노드 2 대신 3을 선택해도 괜찮습니다. 하지만 이 경우에는 정렬 결과가 다릅니다. 앞서 위상 정렬이 늘 같은 정렬 결과를 보장하지 않는다고 말했던 것이 바로 이런 경우를 말합니다.
백준 2252 줄 세우기
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
1. 문제 분석
학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제입니다.
답이 여러 개일 때 아무 것이나 출력해도 된다는 전제는 위상 정렬의 결과값이 항상 유일하지 않다는 알고리즘의 전제와 동일하여 위상 정렬 알고리즘을 사용해야 한다는 사실을 유추할 수 있습니다.
2. 손으로 풀기
1. 인접 리스트에 노드 데이터를 저장하고 진입 차수 배열값을 업데이트합니다.
2. 위상 정렬을 수행합니다.
a. 진입 차수가 0 인 노드를 큐에 저장.
b. 큐에서 데이터를 poll 해서 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소시킵니다.
c. 감소했을 때 진입 차수가 0 이 되는 노드를 큐에 offer 합니다.
d. 큐가 완전히 빌 때까지 a ~ c 을 반복합니다.
🙋 그런데 위상 정렬에서는 사이클이 없어야 하지 않나요? 사이클이 있는지, 없는지에 대한 판별은 하지 않아도 되는 이유가 무엇일까요?
문제에서 두 학생의 키를 비교했을 때의 결과가 입력으로 주어집니다. 만약 A B 가 순서대로 4 2 가 나온다면 4가 2보다 앞에 섭니다. 그렇다면 문제 입력에서 2 4 가 나올 수 없습니다. 4가 2보다 앞에 선다는 조건이 나온 후 2가 4보다 앞에 선다는 조건이 나오면 모순이 되기 때문입니다. 이렇게 애초에 사이클이 형성될 수가 없습니다.
다른 예로 1 2, 2 3 이 문제 입력으로 나오면 3 1 은 문제 입력으로 나올 수 없게 됩니다. 그림으로 그려보면 바로 이해가 될 것입니다.
3. 슈도코드
N: 노드 개수, M: 에지 개수
graph: 그래프 저장 ArrayList<Integer>[]
qu: 위상 정렬을 위해 사용할 큐
Sb: StringBuilder
D[N]: 진입 차수 배열
for(N) { 그래프 생성 }
for(M) { 그래프 에지 데이터 저장, 진입 차수 배열 값 설정 }
for(진입 차수 배열 D 에 대해) { 진입 차수가 0 인 모든 노드 큐에 offer }
while(!qu.isEmpty()) {
cur = 큐에 있는 값 poll
sb.append(cur)
cur 이 가리키는 노드의 진입차수 --;
cur 이 가리키는 노드 중에서 0 이 된 노드를 큐에 offer
}
sb 출력4. 코드
public class BaekJun2252 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] D = new int[N + 1];
ArrayList<Integer>[] graph = new ArrayList[N + 1];
Queue<Integer> qu = new LinkedList<>();
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
graph[A].add(B);
D[B]++;
}
for (int i = 1; i <= N; i++) {
if (D[i] == 0) {
qu.offer(i);
}
}
while (!qu.isEmpty()) {
int cur = qu.poll();
sb.append(cur).append(" ");
for (int adjNode : graph[cur]) {
D[adjNode]--;
if (D[adjNode] == 0) {
qu.offer(adjNode);
}
}
}
System.out.println(sb);
}
}
백준 1516 게임 개발
https://www.acmicpc.net/problem/1516
1516번: 게임 개발
첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부
www.acmicpc.net
1. 문제 분석
어떤 건물을 짓기 위해서 먼저 지어야 하는 건물이 있을 수 있다는 것이 핵심입니다. 각 건물을 노드라고 생각하면 그래프 형태에서 노드 순서를 정렬하는 알고리즘인 위상 정렬을 사용하는 문제라는 것을 알 수 있습니다.
건물 수는 최대 500, 시간 제한은 2초이므로 시간 제한은 여유가 있네요.
2. 손으로 풀기
1. 입력 데이터를 바탕으로 그래프, 진입 차수배열, 정답 배열, 건물 생산 시간 배열을 초기화합니다.
2. 위상 정렬을 실행하면서 각 건물을 짓는데 걸리는 최대 시간을 업데이트합니다.
3. 정답 배열을 차례대로 출력합니다.
3. 슈도코드
N: 건물 종류 수
graph: ArrayList<Integer>[]
build: 각 건물 생산 시간
ans: 정답 배열
inDegree: 진입 차수 배열
qu: 위상 정렬 큐
건물 입력받고 위 자료구조 초기화
qu 에 진입 차수가 0 인 노드들 모두 offer
while(!qu.isEmpty){
qu 에서 poll 하고 node 에 저장
node 이 가리키는 노드들(이하 adjNode) 의 진입 차수--;
ans[adjNode] 의 값 변경
ans[adjNode] 와 ans[node] + build[adjNode] 중 최대값으로.
adjNode 의 진입 차수가 0 인것을 qu 에 offer
}
ans 에 저장된 값을 1 ~ N 까지 출력
4. 코드
public class BaekJun1516Self {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
ArrayList<Integer>[] graph = new ArrayList[N + 1];
int[] build = new int[N + 1];
int[] ans = new int[N + 1];
int[] inDegree = new int[N + 1];
Queue<Integer> qu = new LinkedList<>();
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
int next = Integer.parseInt(st.nextToken());
build[i] = next;
ans[i] = next;
next = Integer.parseInt(st.nextToken());
while (next != -1) {
graph[next].add(i);
inDegree[i]++;
next = Integer.parseInt(st.nextToken());
}
}
br.close();
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) {
qu.offer(i);
}
}
while (!qu.isEmpty()) {
int node = qu.poll();
for (int adjNode : graph[node]) {
inDegree[adjNode]--;
ans[adjNode] = Math.max(ans[adjNode], ans[node] + build[adjNode]);
if (inDegree[adjNode] == 0) {
qu.offer(adjNode);
}
}
}
for (int i = 1; i <= N; i++) {
System.out.println(ans[i]);
}
}
}
백준 1948 임계경로
https://www.acmicpc.net/problem/1948
1948번: 임계경로
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의
www.acmicpc.net
1. 문제 분석
출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상 정렬이 아닌 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로값을 구할 수 있습니다.
이 문제에서 어려운 점은 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는 것입니다. 이를 해결하려면 에지 뒤집기라는 아이디어가 필요합니다.
2. 손으로 풀기
1. 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열 값을 업데이트한다. 이때 에지의 방향이 반대인 역방향 인접 리스트도 함께 생성, 저장한다.
2. 시작 도시에서 위상 정렬을 수행해 각 도시와 관련된 임계 경로를 저장합니다.
3. 도착 도시에서 역방향으로 위상정렬을 수행합니다. 이 때 '이 도시의 임계 경로값 + 도로 시간(에지) == 이전 도시의 임계 경로값' 일 경우에는 이 도로를 1분도 쉬지 않고 달려야 하는 도로로 카운팅하고, 이 도시를 큐에 삽입하는 로직으로 구현해야 합니다.
7의 임계 경로값 = 12 는 1에서 7까지 가는데 가장 오래 걸리는 길임.
2의 임계 경로값 = 4 는 1에서 2 까지 가는데 가장 오래 걸리는 길임.
그리고 노드 7 과 노드 2 사이의 에지에 대해서 이 에지(도로)가 가장 오래 걸리는 경로에 포함된 도로인지 판단하려면
7의 임계 경로값(12) 와 {2의 임계 경로값(4) + 7과 노드 2 사이의 에지 가중치(5)}
이 두 값이 같다면 해당 에지(도로)가 가장 오래 걸리는 경로에 포함된 도로가 된다.
4. 도착 도시의 임계 경로값 12 와 1분도 쉬지 않고 달려야 하는 도로의 수 5을 출력합니다.
※ 노드를 큐에 삽입할 때 주의할 점
1분도 쉬지 않고 달려야 하는 도로로 이어진 노드와 연결된 다른 도로만이 1분도 쉬지 않고 달려야 하는 도로의 후보가 될 수 있습니다.
가장 오래 걸리는 경로에 포함된 도로(에지)로 이어진 노드 X 와 연결된 다른 에지(도로)만 가장 오래 걸리는 경로에 포함된 도로(에지)가 될 수 있으므로 X 의 에지만 조사해나가는 매커니즘으로 하면 된다는 의미입니다.
또한 중복으로 도로를 카운트하지 않기 위해서 이미 방문한 적이 있는 한 노드는 큐에 넣어주지 않습니다.
3. 슈도코드
N: 도시의 개수
M: 도로 수
graph: 정방향 그래프 인접리스트 , inverseGraph: 역방향 그래프 ArrayList<Node>[]
inDegree: 진입차수 배열, criPath: 임계 경로 배열
queue: 위상 정렬 시 사용
for(M){
graph, inverseGraph 초기화
진입차수 배열 초기화
}
start: 출발 도시, arrival: 도착 도시
firstAns: start 에서 arrival 까지 가장 오래 걸리는 경로의 시간
// 정방향 그래프 위상 정렬
queue 에 start 넣기
while(queue 가 빌 때까지){
큐에서 poll 해서 node 에 저장.
node 의 인접 노드(이하 adjNode)의 진입 차수 감소;
adjNode 의 진입차수가 0 이라면 큐에 넣기
adjNode 의 임계 경로 업데이트
이 때 criPath[adjNode] = Math.max(criPath[adjNode], criPath[node] + adjNode의 가중치)
}
firstAns = criPath[arrival]
// 역방향 그래프 위상 정렬
visited: 각 도시의 방문 유무 저장 배열
secondAns : 1분도 쉬지 않고 달려야 하는 도로의 수
queue 에 arrival 삽입.
visited[arrival] = true;
while(queue 가 빌 때까지){
큐에서 poll 해서 node 에 저장
for(node의 에지 adjEdge 들에 대해){
만약 criPath[node] == criPath[adjEdge 의 노드] + adjEdge 의 가중치 이면 {
secondAns++;
만약 아직 방문하지 않았다면 {
큐에 adjEdge 의 노드 offer.
adjEdge 의 노드 방문 기록
}
}
}
}
firstAns 출력
secondAns 출력4. 코드
public class BaekJun1948 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
ArrayList<Edge>[] graph = new ArrayList[N + 1];
ArrayList<Edge>[] inverseGraph = new ArrayList[N + 1];
int[] inDegree = new int[N + 1];
int[] criPath = new int[N + 1];
boolean[] visited = new boolean[N + 1];
Queue<Integer> qu = new LinkedList<>();
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
inverseGraph[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
graph[s].add(new Edge(e, w));
inDegree[e]++;
inverseGraph[e].add(new Edge(s, w));
}
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int arrival = Integer.parseInt(st.nextToken());
int firstAns = 0;
// graph
qu.offer(start);
while (!qu.isEmpty()) {
int node = qu.poll();
for (Edge adjEdge : graph[node]) {
int adjNode = adjEdge.node;
inDegree[adjNode]--;
if (inDegree[adjNode] == 0) {
qu.offer(adjNode);
}
criPath[adjNode] = Math.max(criPath[adjNode], criPath[node] + adjEdge.weight);
}
}
firstAns = criPath[arrival];
int secondAns = 0;
// inverseGraph
qu.offer(arrival);
visited[arrival] = true;
while (!qu.isEmpty()) {
int node = qu.poll();
for (Edge adjEdge : inverseGraph[node]) {
int adjNode = adjEdge.node;
if (criPath[node] == criPath[adjNode] + adjEdge.weight) {
secondAns++;
if (!visited[adjNode]) {
qu.offer(adjNode);
visited[adjNode] = true;
}
}
}
}
System.out.println(firstAns);
System.out.println(secondAns);
}
static class Edge {
int node;
int weight;
public Edge(int node, int weight) {
this.node = node;
this.weight = weight;
}
}
}
'Java > 코딩테스트' 카테고리의 다른 글
| 벨만 포드 알고리즘 자바 백준 BOJ 11657, 1219 (0) | 2023.08.18 |
|---|---|
| 우선순위 큐를 이용한 다익스트라 알고리즘 자바 백준 BOJ 1735, 1916, 1854 (0) | 2023.08.17 |
| 유니온 파인드 자바 백준 BOJ 1717, 1976, 1043 (0) | 2023.08.05 |
| 그래프 표현-2 자바 백준 BOJ 1707, 2251 (0) | 2023.08.05 |
| 그래프 표현-1 자바 백준 BOJ 18352, 1325 (0) | 2023.07.28 |