[BOJ] 1976번 : 여행 가자(Go, Golang)
문제 링크 : 백준 1976번
[문제 접근]
처음에 BFS로 접근했다가 오답을 받아서 다시 생각해보니 m개로 받은 도시가 모두 연결되어 있지 않으면 무조건 불가능이라는 것을 이용해 union find로 풀 수 있을 것 같았다.
- parent배열을 자기 자신으로 초기화해준다.
- n*n번 돌면서 1인 경우에 해당 도시들을 merge해준다.
- find 함수를 이용해 첫 도시를 root 도시로 정하고 m-1번 돌면서 해당 도시가 root도시와 다르면 연결되어 있지 않은 것 이므로
NO
를 출력해주고 그 외의 경우에는YES
를 출력해준다.
⭐ m개의 도시가 모두 연결되어 있다면 root도시는 모두 같아야한다.
[소스 코드]
package main
import (
"bufio"
"fmt"
"os"
)
var (
r = bufio.NewReader(os.Stdin)
w = bufio.NewWriter(os.Stdout)
n, m int
parent [201]int
)
func find(node int) int {
if node == parent[node] {
return node
}
parent[node] = find(parent[node])
return parent[node]
}
func merge(a int, b int) {
a = find(a)
b = find(b)
if a != b {
if a < b {
a, b = b, a
}
parent[b] = a
}
}
func main() {
defer w.Flush()
fmt.Fscan(r, &n, &m)
for i := 1; i <= n; i++ {
parent[i] = i
}
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
var a int
fmt.Fscan(r, &a)
if a == 1 {
merge(i, j)
}
}
}
var a int
check := true
fmt.Fscan(r, &a)
root := find(a)
for i := 1; i <= m-1; i++ {
fmt.Fscan(r, &a)
if root != find(a) {
check = false
}
}
if check {
fmt.Fprintln(w, "YES")
} else {
fmt.Fprintln(w, "NO")
}
}
Author And Source
이 문제에 관하여([BOJ] 1976번 : 여행 가자(Go, Golang)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soosungp33/BOJ-1976번-여행-가자Go저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)