백준 15591번 MooTube (C++)

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

15591번: MooTube (Silver)

 

이제부터 문제를 풀 때 "맞았습니다" 를 보기 위해 집착하기 보다 어떤식으로 사고를 해야할지 생각하면서 풀기로 했다.

 

1. 문제 조건:

 그래프가 주어지고 한 정점이 다른 정점으로 가는 비용 중 가장 적은 간선의 비용을 USADO로 결정한다. 즉, 지나온 간선 중 가장 적은 비용이 유사도이다.

 

2. 내 접근

먼저 한 정점에서 다른 모든 정점까지의 최소 간선 비용을 얻으면 된다고 생각했다. 그래서 다익스트라 알고리즘이 생각났는데, 문제는 비싼 비용으로 다른 정점에 도착해도 가장 낮은 간선의 비용을 포함하고 있을 수 있었다. 

이것이 첫번째 패착이었다.

 

3. 올바른 접근법

먼저 생각한것은 dfs 백트레킹으로 모든 정점을 계속 방문하며 테이블을 만드는 것이었다. 그러나 이것은 TLE의 가능성이 농후하다.

 

 가장 가까운 정점부터 방문해가며 답을 업데이트해가는 것이 올바른 접근법이다. bfs조건으로 방문하지 않았고, 다음 간선의 비용이 k보다 크다면 이동한다. 

증명을 해보면 

 

k = 5 라고 가정하자. 그렇다면 1에서 2로 갈 때 4라면 이 다음에 나올 유사도는 언제나 4보다 작다. 그러므로 더이상 방문해줄 필요가 없다.

 

if(방문한 적이 없음 and k 이상임){
	q에 삽입
    방문표시
    카운트++
}

이것이 기본 bfs 로직이다.

 

정답 코드는 다음과 같다.

 

#include <iostream>
#include <queue>
using namespace std;

int N, Q;
bool check[5001];
vector<pair<int, int>> Node[5001];

void bfs(int start, int k) {
	queue<int> q;
	check[start] = true;
	q.push(start);
	int cnt = 0;
	while (!q.empty()) {
		int nownode = q.front();
		q.pop();
		for (int i = 0; i < Node[nownode].size(); i++) {
			int nextnode = Node[nownode][i].first;
			int Cost = Node[nownode][i].second;
			//cout << "========" << nextnode << " " << Cost << endl;
			
			if (check[nextnode] == false && Cost >= k) {
				//cout << Cost << endl;
				q.push(nextnode);
				check[nextnode] = true;
				cnt++;
			}
		}
	}
	cout << cnt << '\n';
}

void init() {
	for (int i = 0; i <= N; i++) {
		check[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> Q;
	for (int i = 0; i < N - 1; i++) {
		int st, ed, value;
		cin >> st >> ed >> value;
		Node[st].push_back({ ed, value });
		Node[ed].push_back({ st, value });
	}

	for (int i = 0; i < Q; i++) {
		int start, k;
		cin >> start >> k;
		init();
		bfs(k, start);
		//cout << cnt << '\n';
	}
}

다익스트라에 꽂혀서 엄청 틀렸다.