[백준] 25953번 템포럴 그래프 C++ 문제풀이

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

25953번: 템포럴 그래프

문제 풀이

맨 처음에 그래프 탐색 문제인 줄 알고 DFS라고 함수명을 정한 뒤 문제를 풀었는데, 적는 지금 생각해보니 그냥 DP문제였다.

1차원 배열로 DP를 해결하려 했으나 39%에서 계속 틀리길래 왜 그런지 생각해보았는데, 알고보니 1차원 배열로 갱신하게 되면 중간에 값이 바뀌기 때문에 틀리게 되어버린다.

void dfs(int s_time) {
	if (s_time == t) {
		return;
	}
	for (int i = 0; i < graph[s_time].size(); i++) {
		pair<int, int> direction = graph[s_time][i].first;
		int start_p = direction.first;
		int end_p = direction.second;
		move_p[end_p] = min(move_p[end_p], move_p[start_p] + graph[s_time][i].second);
		move_p[start_p] = min(move_p[start_p], move_p[end_p] + graph[s_time][i].second);
	}
	dfs(s_time + 1);
}

위 처럼 함수를 작성하면 for문 안에서 값이 갱신 되기 때문에 DP를 적용할 수 없다

해결 방법으로 2가지를 생각했는데,

첫번째는 배열을 복사하는 것이다.

void dfs(int s_time) {
	if (s_time == t) {
		return;
	}
	std::copy(std::begin(move_p), std::end(move_p), std::begin(move_p_t));
	for (int i = 0; i < graph[s_time].size(); i++) {
		pair<int, int> direction = graph[s_time][i].first;
		int start_p = direction.first;
		int end_p = direction.second;
		move_p[end_p] = min(move_p[end_p], move_p_t[start_p] + graph[s_time][i].second);
		move_p[start_p] = min(move_p[start_p], move_p_t[end_p] + graph[s_time][i].second);
	}
	dfs(s_time + 1);
}

위와 같이 for문 이전에 t-1시점의 move_p 배열을 move_p_t 배열에 복사하면 된다.

 

두번째 방법은 이차원 배열을 만드는 것이다.(move_p[시간][정점] 이런식으로...)

void dfs(int s_time) {
	if (s_time == t) {
		return;
	}
	for (int j = 0; j < n; j++) {
		move_p[s_time + 1][j] = move_p[s_time][j];
	}
	for (int i = 0; i < graph[s_time].size(); i++) {
		pair<int, int> direction = graph[s_time][i].first;
		int start_p = direction.first;
		int end_p = direction.second;
		move_p[s_time + 1][end_p] = min(move_p[s_time + 1][end_p], move_p[s_time][start_p] + graph[s_time][i].second);
		move_p[s_time + 1][start_p] = min(move_p[s_time + 1][start_p], move_p[s_time][end_p] + graph[s_time][i].second);
	}
	dfs(s_time + 1);
}

소스 코드

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

int n, t, m, s_point, e_point;
vector<pair<pair<int, int>, int>> graph[1001];
int move_p[1001][10001] = {0};

void dfs(int s_time) {
	if (s_time == t) {
		return;
	}
	for (int j = 0; j < n; j++) {
		move_p[s_time + 1][j] = move_p[s_time][j];
	}
	for (int i = 0; i < graph[s_time].size(); i++) {
		pair<int, int> direction = graph[s_time][i].first;
		int start_p = direction.first;
		int end_p = direction.second;
		move_p[s_time + 1][end_p] = min(move_p[s_time + 1][end_p], move_p[s_time][start_p] + graph[s_time][i].second);
		move_p[s_time + 1][start_p] = min(move_p[s_time + 1][start_p], move_p[s_time][end_p] + graph[s_time][i].second);
	}
	dfs(s_time + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> t >> m >> s_point >> e_point;
	
	for (int i = 0; i < t; i++) {
		for (int j = 0; j < m; j++) {
			int s, e, w;
			cin >> s >> e >> w;
			graph[i].push_back(make_pair(make_pair(s, e), w));
		}
	}

	for (int i = 0; i < n; i++) {
		move_p[0][i] = 1000000007;
 	}
	move_p[0][s_point] = 0;

	dfs(0);

	int result = move_p[t][e_point];
	if (result >= 1000000007)
		cout << "-1" << '\n';
	else 
		cout << result << '\n';

}