[C/C++] 백준 - 14218번 : 그래프 탐색 2

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

14218번: 그래프 탐색 2

문제

남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 있는 도로들을 새로 만드는 계획이다. 도로 정비 계획은 두 도시에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다.

Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.

남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오.

 

 

도시를 연결하는 도로의 정보가 주어질 때, 각각의 도시에서 수도로 이동하는 최소 이동 비용을 구하는 문제이다.

도로의 정보가 갱신될 때마다 도시들의 상태가 달라지기 때문에 이 점을 고려하지 않는 방법은 떠오르지 않았다.

 

도로의 정보가 갱실될 때마다 처음부터 모든 도시들을 완전탐색을 진행한다. 하지만 각 도시를 진행하다보면 같은 경로를 지나가야하는 구간이 분명히 존재한다. 이를 메모이제이션 기법을 적용하여 좀 더 효율적인 코드로 작성할 수 있도록 해야한다.

 

추가적인 정보가 아닌 가장 처음에 주어지는 정보에서 수도(1번)와 연결된 도시들은 벡터에 저장해두어 도로 정보를 갱실할 때 메모이제이션을 바로 1로 적용시켜주도록 한다. 그리고 그 외의 정보만을 완전탐색 + 메모이제이션, 즉 동적계획법을 이용한다.

 

---

#include <iostream>
#include <vector>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl

using namespace std;

int N, M, Q;
vector<int> v;
ll cache[1000 + 1];
vector<int> adj[1000 + 1];

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);

		if (a == 1 || b == 1) {
			a == 1 ? v.push_back(b) : v.push_back(a);
		}
	}
}

ll path(int prev, int node) {
	if (node == 1) return 0;
	ll& ret = cache[node];
	if (ret != INF && ret != -1) return ret;

	ret = INF;
	for (auto& t : adj[node]) {
		if (t == prev) continue;
		ret = min(ret, path(node, t) + 1);
	}
	return ret;
}

void init() {
	for (auto t : v) cache[t] = 1;
}

void solution() {
	cin >> Q;
	while (Q--) {
		int node1, node2;
		cin >> node1 >> node2;
		adj[node1].push_back(node2);
		adj[node2].push_back(node1);

		memset(cache, -1, sizeof(cache));
		init();

		int dist;
		for (int node = 1; node <= N; node++) {
			if (node == 1) {
				cache[node] = 0;
				cout << 0 << " ";
				continue;
			}
			path(-1, node);
			cache[node] == INF ? cout << -1 << " " : cout << cache[node] << " ";
		}
		ENDL;
	}
}

int main() {
	fastio;
	input();
	solution();

	return 0;
}