백준 15591번: MooTube(Silver)

❓ 문제

15591번: MooTube (Silver)

유사도, 최솟값의 단어를 도입해 엄청나게 어렵게 보이게 만든 문제
특히 힌트가 날 더 어렵게 했다... 🤔
사실 평범한 그래프 탐색을 조금 응용하는 문제이다

💡 풀이

1. 문제에 주어진 동영상 V를 탐색을 시작할 노드로 잡는다.
2. BFS로 주변 노드를 검색하면서 가중치가 K 이상일 때는 BFS의 Queue에 추가한다. 즉, 방문한 노드의 주변 노드도 방문할 수 있게 한다.
3. 그렇지 않다면 큐에 추가하지 않는다.
   • K = 3 일 때, A, B가 유사도 2로 연결되어 있고 B, C가 유사도 4로 연결되어 있을 때, A, C는 유사도 2를 가지기 때문이다. 즉 B와 연결된 동영상은 모두 A와 유사도 2로 연결되어 있기 때문에 아예 방문할 필요가 없다.
4. result에 1을 더한다.
5. 모든 영상을 다 돌았으면 result를 반환한다.

⌨️ 전체 코드

package main

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

type Graph struct {
	nodes []int
	edges map[int][]*Node
}

type Node struct {
	value  int
	weight int
}

func (graph *Graph) addNode(node int) {
	graph.nodes = append(graph.nodes, node)
}

func (graph *Graph) addEdge(node1, node2 int, weight int) {
	if graph.edges == nil {
		graph.edges = make(map[int][]*Node)
	}
	graph.edges[node1-1] = append(graph.edges[node1-1], &Node{node2, weight})
	graph.edges[node2-1] = append(graph.edges[node2-1], &Node{node1, weight})
}

type Queue struct {
	queue []int
}

func (q Queue) isEmpty() bool {
	return len(q.queue) == 0
}

func (q *Queue) enqueue(data int) {
	q.queue = append(q.queue, data)
}

func (q *Queue) dequeue() int {
	if q.isEmpty() {
		return -1
	}
	data := q.queue[0]
	q.queue = q.queue[1:]
	return data
}

func (graph Graph) search(root, k int) int {
	result := 0
	queue := Queue{}
	visited := map[int]bool{}

	visited[root-1] = true
	queue.enqueue(root)

	for !queue.isEmpty() {
		n := queue.dequeue()
		nodes := graph.edges[n-1]
		for _, node := range nodes {
			if !visited[node.value-1] {
				visited[node.value-1] = true
				if node.weight >= k {
					result++
					queue.enqueue(node.value)
				}
			}
		}
	}

	return result
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	N, Q := 0, 0
	fmt.Fscan(reader, &N, &Q)

	graph := Graph{}
	for i := 0; i < N; i++ {
		graph.addNode(i)
	}
	for i := 0; i < N-1; i++ {
		p, q, r := 0, 0, 0
		fmt.Fscan(reader, &p, &q, &r)
		graph.addEdge(p, q, r)
	}

	result := []int{}
	for i := 0; i < Q; i++ {
		k, v := 0, 0
		fmt.Fscan(reader, &k, &v)
		result = append(result, graph.search(v, k))
	}

	for _, v := range result {
		fmt.Fprintln(writer, v)
	}
}

🔁 삽질

처음 아이디어는 다른 연결되어 있지 않은 노드들도 BFS로 통해 최소 가중치를 찾아내 연결하려고 생각했다. 덕분에 가중치들의 최솟값을 어떻게 구해야 하는지 몰라 너무 헤맸다. 결국 구글링을 해 푸는 법을 알아내니 너무나도 허탈했다. 그냥 그 노드를 방문할 필요가 없는데... 😓

📖 새롭게 배운 내용

❌

💫 헷갈리는 부분

❌

📚 참고 자료

[백준 15591 C++][G5] MooTube(Silver)