[GoLang] 백준 1005번, ACM Craft(위상 정렬)

개요

문제  https://www.acmicpc.net/problem/1005

📃 해당 문제는 이전에 풀었던 위상 정렬 문제인 2252번을 이용하시면 쉽게 이해할 수 있습니다.

https://seung.tistory.com/entry/GoLang-%EB%B0%B1%EC%A4%80-2252%EB%B2%88-%EC%A4%84-%EC%84%B8%EC%9A%B0%EA%B8%B0%EC%9C%84%EC%83%81%EC%A0%80%EB%A0%AC

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

같은 알고리즘인 위상 정렬에다가 노드 별로 가중치(시간)을 잘 녹이면 됩니다.

 

아래 그림으로 이해해봅시다.

화살표가 방향, 원 위의 숫자가 그 노드의 시간입니다.

특정 노드까지의 시간의 총합을 알려면 이전의 값들을 다 더하면 됩니다.

이런 식으로 나오는 데 각 노드의 합의 경우

전체 노드의 개수만큼의 리스트를 만든 후 거기서 이전 노드의 값과 현재 노드 값을 저장하게 로직을 구성하면

간단하게 해결 됩니다.

 

그리고 그림처럼 7번 노드는 이전 값 중 큰 값을 기준으로 가져오면됩니다.

(이전 노드가 전부 완료되어야 하므로 가장 큰 수를 가져야 합니다.)

코드

아래 코드를 보시면 이전 위상정렬 문제에서 조금만 달라진 것을 느낄 수 있을 겁니다

달라진 점은

• 각 노드별 건설 시간을 담은 리스트
• 각 노드까지의 건설 시간을 담은 리스트
• 목표 건물에 진입차수가 없을 경우 예외 처리
• 각 노드별에 접근하는 가장 큰 시간 값을 저장
• 목표 노드가 나오면 종료

package main

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

func main() {
	// 테스트 케이스만큼 반복
	reader := bufio.NewReader(os.Stdin)
	var testCases int
	fmt.Fscanln(reader, &testCases)
	for i := 0; i < testCases; i++ {
		acmCraft(reader)
	}
}

func acmCraft(reader *bufio.Reader) {
	// 건물 수 n, 건물 순서 k, 목표 건물 번호 w 입력
	var n, k, w int

	// 건물 수, 순서 입력
	fmt.Fscanln(reader, &n, &k)

	// n+1을 하는 이유는 계산의 편의를 위해 0 인덱스를 사용하지 않기 위함
	// 인접 리스트, 크기 비교를 해서 작은 수(key) -> 큰 수(value)로 되게 저장할 예정
	adjList := make([][]int, n+1)
	// 건물 당 건설에 걸리는 시간
	buildTime := make([]int, n+1)
	// 진입 차수
	inDegree := make([]int, n+1)
	// 걸리는 시간
	buildTotalTime := make([]int, n+1)

	// 건물 당 건설에 걸리는 시간 입력
	for i := 1; i <= n; i++ {
		fmt.Fscan(reader, &buildTime[i])
	}
	fmt.Fscanln(reader)

	// 건물 순서 입력
	for i := 0; i < k; i++ {
		var prev, next int
		fmt.Fscanln(reader, &prev, &next)
		// 건물 번호로 작은 수 -> 큰 수로 저장
		adjList[prev] = append(adjList[prev], next)
		// 큰 수의 진입 차수 증가
		inDegree[next]++
	}

	// 목표 건물 번호 입력
	fmt.Fscanln(reader, &w)

	// 진입 차수가 0인 것을 큐에 넣음
	queue := []int{}
	for i := 1; i <= n; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
			buildTotalTime[i] = buildTime[i]
		}
	}

	// 목표 건물을 바로 지을 수 있는 경우 반환
	if inDegree[w] == 0 {
		fmt.Println(buildTime[w])
		return

	}

	// 큐가 빌때 까지 정렬
	for len(queue) > 0 {
		// 큐에서 값을 꺼냄
		current := queue[0]
		queue = queue[1:]

		// 큐에서 꺼낸 값과 연결된 노드들의 진입 차수를 1씩 감소
		for _, next := range adjList[current] {
			// 각 노드별로 가장 오래 걸리는 시간을 저장
			if buildTotalTime[next] < buildTotalTime[current]+buildTime[next] {
				buildTotalTime[next] = buildTotalTime[current] + buildTime[next]
			}
			// 진입 차수가 0이 되면 큐에 넣음
			inDegree[next]--
			if inDegree[next] == 0 {
				// 만약 목표 건물이 진입 차수가 0이 되면 그 건물의 건설 시간을 출력하고 종료
				if next == w {
					fmt.Println(buildTotalTime[next])
					return
				}
				queue = append(queue, next)
			}
		}
	}

}