[BOJ] 1939번 : 중량제한(Go, Golang)

문제 링크 : 백준 1939번

[문제 접근]

중량 제한의 최대값이 1,000,000,000이라 그냥 BFS 탐색으로는 풀면 최악의 경우 1,000,000,000인 경우까지 탐색해야 하므로 시간초과가 발생한다. 따라서 이분탐색을 사용해 값을 정하고 BFS를 통해 탐색했다.

1. arr 슬라이스의 a 인덱스에 b 인덱스와 cost를 저장해주고 그 반대도 똑같이 해준다.
2. 이분 탐색을 통해 mid 값을 설정해주고 BFS를 통해 탐색한다.
3. mid 중량으로 A공장에서 B공장으로 갈 수 있다면 start = mid + 1
4. 갈 수 없다면 end = mid - 1
5. 조건에 만족하지 않을 때까지 반복하면 end에 답이 저장된다.

⭐️ start와 end가 같은 상황까지오면 그게 정답이므로 re가 true가되서 start가 end보다 1 커진다. 따라서 end가 정답이고 start는 정답 + 1이 저장된다.

[소스 코드]

package main

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

type node struct {
	f    int
	cost int
}

var (
	r            = bufio.NewReader(os.Stdin)
	w            = bufio.NewWriter(os.Stdout)
	n, m, fa, fb int
	arr          [10001][]node
	ans          int
	re           bool
)

func BFS(mid int) {
	var visit [10001]bool
	q := []int{fa}
	visit[fa] = true

	for len(q) > 0 {
		x := q[0]
		q = q[1:]

		if x == fb {
			if ans < mid {
				ans = mid
			}
			re = true
			continue
		}

		for i := 0; i < len(arr[x]); i++ {
			nx := arr[x][i].f
			if !visit[nx] {
				if arr[x][i].cost >= mid {
					q = append(q, nx)
					visit[nx] = true
				}
			}
		}
	}
}

func main() {
	defer w.Flush()
	fmt.Fscan(r, &n, &m)

	for i := 0; i < m; i++ {
		var a, b int
		var c int
		fmt.Fscan(r, &a, &b, &c)
		arr[a] = append(arr[a], node{f: b, cost: c})
		arr[b] = append(arr[b], node{f: a, cost: c})
	}
	fmt.Fscan(r, &fa, &fb)

	// 이분 탐색
	var start, end int
	start = 1
	end = 1000000000
	for start <= end {
		var mid int
		mid = (start + end) / 2
		BFS(mid)
		if re { // start와 end가 같은 상황까지오면 그게 정답이므로 re가 true가되서 start가 end보다 1 커진다. 따라서 end가 정답
			start = mid + 1
		} else {
			end = mid - 1
		}
		re = false
	}
	fmt.Fprintln(w, end)
}