[BOJ] 1976번 : 여행 가자(Go, Golang)

문제 링크 : 백준 1976번

[문제 접근]

처음에 BFS로 접근했다가 오답을 받아서 다시 생각해보니 m개로 받은 도시가 모두 연결되어 있지 않으면 무조건 불가능이라는 것을 이용해 union find로 풀 수 있을 것 같았다.

1. parent배열을 자기 자신으로 초기화해준다.
2. n*n번 돌면서 1인 경우에 해당 도시들을 merge해준다.
3. 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")
	}

}