[Go] 백준 1005번 (위상 정렬, 깊이 우선 탐색)

문제

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

입력

첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설 순서 규칙의 총 개수 K가 주어진다. (건물의 번호는 1번부터 N번까지 존재한다.)

둘째 줄에는 각 건물당 건설에 걸리는 시간 D1, D2, ..., Dn이 공백을 사이로 주어진다. 셋째 줄부터 K+2줄 까지 건설 순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다.)

마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 W가 주어진다.

2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7

출력

건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.

건설순서는 모든 건물이 건설 가능하도록 주어진다.

120
39

---

문제 풀이

문제 해석 및 계획

목표하는 건물을 짓기 위해서는 연결된 건물들을 순서대로 지어야하기에 경로를 찾아야한다고 생각하였습니다.

목표 건물로 향하지 않는 경로는 제거하기 위하여 목표 건물에서 역순으로 건물을 짓는데 걸리는 시간을 측정하기로 생각하였습니다.

해당 경로중에 가장 오래 걸린 시간이 답이라고 생각하였기 때문에 DFS라고 예상을 하였습니다.

역순으로 건물의 시간을 확인하기에 각 건물부터 목표건물까지 걸리는 시간을 확인해두어야하기에 check라는 슬라이스 생성하여 각 건물마다 목표 건물까지 걸리는 시간을 기록하였습니다.

오답 노트

package main

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

func main(){
	rx := bufio.NewReader(os.Stdin)
	wx := bufio.NewWriter(os.Stdout)
	
	defer wx.Flush()
	
	var testNum int
	fmt.Fscan(rx, &testNum)
	for i:=0 ; i<testNum ; i++ {
		var buildNum, ruleNum int
		var winBuild int
		fmt.Fscan(rx, &buildNum, &ruleNum)
		buildTime := make([]int,buildNum+1)
		buildRule := make([][]int,buildNum+1)
		for j := 1 ; j<=buildNum ; j++{
			fmt.Fscan(rx,&buildTime[j])
		}
		for k:=1 ; k<=ruleNum ; k++{
			var key, value int
			fmt.Fscan(rx, &value, &key)
			buildRule[key]=append(buildRule[key],value)
		}
		fmt.Fscan(rx,&winBuild)

		fmt.Fprintln(wx,DFS(buildTime, buildRule, winBuild))
	}
}

func DFS(buildTime []int, buildRule [][]int, winBuild int)int{
	stack := make([]int,0)
	stack = append(stack,winBuild)
	check := make([]int,len(buildTime)+1)
	answer := 0
	copy(check,buildTime)
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		for _, neighbor := range buildRule[node]{
			if check[neighbor] < check[node] + buildTime[neighbor]{
				check[neighbor] = check[node] + buildTime[neighbor]
			}
			if answer < check[neighbor]{
				answer = check[neighbor]
			}
			stack=append(stack,neighbor)
		}
	}
	return answer
}

결과는 시간초과였습니다.

저에게는 가장 어려운 시간 줄이기를 하여야합니다.

정답

package main

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

func main(){
	rx := bufio.NewReader(os.Stdin)
	wx := bufio.NewWriter(os.Stdout)
	
	defer wx.Flush()
	
	var testNum int
	fmt.Fscan(rx, &testNum)
	for i:=0 ; i<testNum ; i++ {
		var buildNum, ruleNum int
		var winBuild int
		fmt.Fscan(rx, &buildNum, &ruleNum)
		buildTime := make([]int,buildNum+1)
		buildRule := make([][]int,buildNum+1)
		inDegree := make([]int,buildNum+1)
		for j := 1 ; j<=buildNum ; j++{
			fmt.Fscan(rx,&buildTime[j])
		}
		for k:=0 ; k<ruleNum ; k++{
			var key, value int
			fmt.Fscan(rx, &key, &value)
			buildRule[key]=append(buildRule[key],value)
			inDegree[value]++
		}
		fmt.Fscan(rx,&winBuild)

		fmt.Fprintln(wx,TS(buildTime, buildRule, inDegree, winBuild))
	}
}
func TS(buildTime []int, buildRule [][]int, inDegree []int, winBuild int)int{
	queue := make([]int,0)
	for j:=0 ; j<len(buildTime) ;j++{
		if inDegree[j] == 0 {
			queue = append(queue,j)
		}
	}
	rst := make([]int,len(buildTime))
	copy(rst,buildTime)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		for _, neighbor := range buildRule[node]{
			inDegree[neighbor]--
			if rst[neighbor] < rst[node]+buildTime[neighbor]{
				rst[neighbor] = rst[node]+buildTime[neighbor]
			}
			if inDegree[neighbor] == 0 {
				queue=append(queue,neighbor)
			}
		}
	}
	return rst[winBuild]
}

깊이우선탐색이 아닌 위상정렬을 사용하여야 시간초과가 발생하지 않는 문제였습니다.

---

느낀 점 & 배운 점

변수 입력 받기

건물당 건설에 걸리는 시간을 입력 받는 것에서 처음 멈추게 되었습니다.

총 건물의 수를 입력받기 때문에 Fscan에 미리 특정 변수를 지정해둘 수 없어 고민에 빠졌습니다.

입력을 어떻게 받아야 하며 받는 값의 개수가 상황마다 다른데 어떻게 처리할 수 있을까 고민하던 중

Fscan과 Fscanln을 혼용하였을 때 생긴 문제가 떠올랐고 여러개의 변수를 한 줄에 띄어쓰기로 분류하여 입력하면 Fscan은 띄어쓰기를 기준으로 Fscan에 작성된 값에 입력할 것이라고 생각하여 map과 for문을 이용하여 입력을 처리하였습니다.

이전에 오류를 경험하지 않고 Fscan에 입력받을 변수들을 모두 기입해둔 예시들만 보았다면 떠올리지 못했을 방법입니다.

문제를 풀다보면 오류를 마주하게 되어 답답할 때도 있지만 경험으로 쌓이다보면 활용할 수 있게 되어 실력이 되기에 오류에서도 배우겠다는 마음을 가지게 되었습니다.

위상정렬과 깊이우선탐색

문제를 받고 DFS를 떠올리게 되었습니다. 해결 방법을 발견하게되어 기쁜마음에 프로그래밍을 하였지만 시간초과라는 벽을 마주하게되었습니다.

이전에 학습해본 알고리즘은 BFS와 DFS가 전부였기에 시간을 줄일 방법으로 struct를 지워보고 코드도 간소화해보았지만 역시 이러한 수정으로 많은 시간을 줄일 수 없었습니다.

결국 해결방법을 위하여 검색을 하게 되었고 위상정렬을 알게되었습니다.

제가 보기엔 위상정렬의 경우 모든 건물에 대하여 걸리는 시간을 체크하게 되는데 목표 건물부터 역순의 경우 필요한 경로만 확인하기에 더 빠를 것이라는 생각에 Go언어의 benchmark를 활용하여 테스트를 하였습니다.

*모든 경우의 수는 아니기에 제가 생각못한 원인 있을 수 있습니다.

package main

import "testing"

func BenchmarkTestDFS(b *testing.B){
	for i:=0 ; i<b.N ; i++{
		DFS([]int{0,10,1,100,10},[][]int{{},{},{1},{1},{2,3}},4)
		DFS([]int{0,10,20,1,5,8,7,1,43},[][]int{{},{},{},{},{},{},{},{},{}},7)
		DFS([]int{0,1,2,3},[][]int{{},{},{1},{2}},1)
		DFS([]int{0,5,5,5,5},[][]int{{},{},{1},{1,2},{}},4)
		DFS([]int{0,100000,99999,99997,99994,99990},[][]int{{},{},{1},{1,2},{1,2,3},{1,2,3,4}},4)
	}
}

func BenchmarkTestTS(b *testing.B){
	for i:=0 ; i<b.N ; i++{
		TS([]int{0,10,1,100,10},[][]int{{},{2,3},{4},{4},{}},[]int{0,0,1,1,2},4)
		TS([]int{0,10,20,1,5,8,7,1,43},[][]int{{},{2,3},{4,5},{6},{},{7},{7},{8},{}},[]int{0,0,1,1,1,1,1,2,1},7)
		TS([]int{0,1,2,3},[][]int{{},{2},{3},{}},[]int{0,0,1,1},1)
		TS([]int{0,5,5,5,5},[][]int{{},{2,3},{3},{},{}},[]int{0,0,1,2,0},4)
		TS([]int{0,100000,99999,9997,9994,9990},[][]int{{},{2,3,4,5},{3,4,5},{4,5},{5},{}},[]int{0,0,1,2,3,4},4)
	}
}

BenchmarkTest 결과

역시 DFS가 빠른 것을 보여주었습니다.

원인은 모르겠지만 이번 문제를 통하여 위상정렬을 배우게되었으므로 얻어가는 것이 있었던 문제였습니다.