[GoLang] 백준 2252번, 줄 세우기(위상 정렬)

개요

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

📃 해당 문제는 위상 정렬로 해결할 수 있습니다.

이를 알 수 있는 이유는 키를 비교하는 것이기에 만약 1번이 2번보다 작다, 2번은 3번보다 작다 근데 3번이 1번 보다

작다와 같이 순환되지 않는다는 걸 의미합니다

 

거기에 문제에서 답이 여러 가지인 경우 아무거나 출력한다고 말했으니 그 말은

비교했을 때 순서가 동일한 게 생긴다는 의미입니다.

이걸로 위상 정렬이라는 것을 추론할 수 있습니다.

 

위상 정렬

💡 그러면 위상정렬이란?

방향이 존재하지만 순환이 되지 않는 그래프의 점들이 변의 방향을 거스르지 않고 나열된 것을 의미합니다.

말로만 보면 어려울 수 있으나 일상생활에서 자주 접할 수 있습니다

 

예를 들면 스타크래프트라는 게임에서 게이트웨이라는 건물을 짓기 위해서는 아래의 조건을 만족해야 합니다.

하지만 꼭 순서가 정해져 있지 않죠, 미네랄을 먼저 모을 수 있고 파일럿을 먼저 지을 수 있습니다.

• 미네랄을 150개 모은다.
• 파일럿을 건설한다.

그 다음 드라곤이라는 유닛을(몬스터) 뽑으려면 또 아래 조건을 만족해야 하죠

• 게이트웨이를 건설한다.
• 사이버네틱스 코어를 건설한다.
• 미네랄 125와 가스 50을 모아 게이트웨이에서 생성한다.

해야 할 일이 점이고 순서가 변의 방향이라고 이해하면 됩니다.

 

🖼 아래 그림을 통해 이해해 봅시다.

1번이 시작 값이므로 큐에 보냅시다, 1번이 시작인 이유를 1번을 가리키는 노드(점)가 없기 때문입니다.

이제 1번을 만족해야 할 수 있는 2번, 4번을 해결할 수 있습니다.

이를 알고리즘으로 볼 때는 진입 차수(접근하는 변)가 없을 때를 의미하는데 우리는 진입 차수가 없는 값을 큐에 적재합니다.

 

1번도 처음에는 진입 차수가 0이었음을 알면 이해하기 쉽습니다.

그래서 지금은 2번, 4번이 진입차수가 0이네요.

이제 3번 그림에서 2번, 4번을 가져다가 큐에 넣습니다.

이때 3번 그림에서 진입 차수가 0인 노드(점)가 3번, 6번이 생겼네요

이를 4번 그림에서 처럼 큐에 넣어두면 마지막 노드 5가 남습니다 이것도 큐에 넣으면 됩니다.

큐는 FIFO(선입선출)이므로 이를 출력하면 다음과 같은 결과 값이네요

1,2,4,3,6,5

 

이를 문제에 적용해 키가 작은 값이 큰 값을 가리키는 변(방향)을 가지게 함으로써

문제를 해결할 수 있습니다.

 

코드

코드의 논리 흐름은 다음과 같습니다.

1. 노드의 방향을 담을 인접 리스트를 만든다
2. 각 노드별로 진입 차수가 몇이 남은 지를 나타내기 위한 배열을 만든다
3. 위상 정렬 순서를 저장할 배열(큐)을 만든다
4. 인접 리스트에 방향을 나타낼 수 있게 값을 입력받는다.
5. 이를 나타내기 위해 문제에서 뒤에 나타나야 할 값들을 기준으로 진입 차수 배열에서 값을 증가한다.
6. 이제 진입 차수가 0인 값부터 큐에 넣는다
7. 큐가 빌 때까지 큐에 있는 값을 꺼내 인접된 값들의 진입차수를 감소시키는데 만약 0이 된다면 큐에 넣는다.
8. 7번에서 값을 꺼낼 때 그 값을 출력하면 된다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	// 학생 수, 크기 비교 수 입력
	reader := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscanln(reader, &n, &m)

	// n+1을 하는 이유는 계산의 편의를 위해 0 인덱스를 사용하지 않기 위함
	// 인접 리스트, 크기 비교를 해서 작은 수(key) -> 큰 수(value)로 되게 저장함
	adjList := make([][]int, n+1)
	// 진입 차수 리스트, 각 노드에 들어오는 진입 차수의 수를 나타냄
	inDegree := make([]int, n+1)

	// 크기 비교들을 입력 받음
	for i := 0; i < m; i++ {
		var s, t int
		fmt.Fscanln(reader, &s, &t)
        // 작은 값이 큰 값을 향하게(방향대로)
		adjList[s] = append(adjList[s], t)
		// 큰 값에 진입 차수가 있다는 의미이므로 값을 증가
		inDegree[t]++
	}

	// 큐를 이용한 위상 정렬
	queue := []int{}
	for i := 1; i <= n; i++ {
		// 진입 차수가 0인 것을 큐에 넣음
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	// 큐가 빌때 까지 정렬
	for len(queue) > 0 {
		// 큐에서 값을 꺼냄
		current := queue[0]
		queue = queue[1:]
		// 뽑은 값을 그대로 출력
		fmt.Print(current, " ")

		// 큐에서 꺼낸 값과 연결된 노드들의 진입 차수를 1씩 감소
		for _, next := range adjList[current] {
			inDegree[next]--
			// 진입 차수가 0이 되면 큐에 넣음
			if inDegree[next] == 0 {
				queue = append(queue, next)
			}
		}
	}
}