BOJ 1956

28 Jan 2020 • ProblemSolving

운동

문제출처

1.설계(15)

  • 문제 해석

    • V개의 마을과 E개의 단방향 도로가 있는데 이 중, 사이클을 이루는 도로 길이 합의 최소를 구하는 문제입니다.
    • 2 <= V <= 400, 0 <= E <= V*(V-1)

  • 설계

    • 전형적인 플로이드-와샬문제이지만 dfs만으로도 충분히 구현이 가능할 것 같았습니다.

    • 가능한 이유는 다음과 같이 생각하였습니다.

      a. 사이클의 길이 합의 최소는 정점을 시작점을 제외하고 한번만 방문해야 합니다.

      b. 여러번 방문했다는 것은 그보다 더 작은 사이클이 존재하다는 뜻으로 이해하였습니다. 해당 사이클은 다른 정점에서 체크를 할 수 있습니다.

      c. 여러개의 간선이 한개의 정점으로 모이는 경우에는 어차피 모든 정점을 기준으로 하여 탐색을 하면 충분히 커버되는 문제라고 생각했습니다.

2.구현(60)

  • 코드 1 (플로이드-와샬 알고리즘)
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 400
#define INF 987654321
using namespace std;

int adj[MAXN][MAXN];
int N, M;
int ans = INF;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			adj[i][j] = INF;
		}
	}
	for (int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u-1][v-1] = w;
	}
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (ans > adj[i][i]) ans = adj[i][i];
	}
	if (ans == INF) cout << "-1\n";
	else cout << ans << "\n";
	return 0;
}
  • 코드 2 (dfs)
#include <iostream>
#include <cstring>

#define MAXN 400
#define INF 987654321
using namespace std;

int adj[MAXN][MAXN];
int N, M;
int ans = INF;
bool visited[MAXN];
void dfs(int cur, int target, int cnt) {
	if (ans <= cnt) return;
	visited[cur] = true;
	for (int i = 0; i < N; i++) {
		if (adj[cur][i] == 0) continue;
		if (i == target) {
			if (ans > cnt + adj[cur][i]) {
				ans = cnt + adj[cur][i];
				return;
			}
		}
		if (visited[i]) continue;
		dfs(i, target, cnt + adj[cur][i]);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	
	for (int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u - 1][v - 1] = w;
	}
	for (int i = 0; i < N; i++) {
		memset(visited, false, sizeof(visited));
		dfs(i, i, 0);
	}
	
	if (ans == INF) cout << "-1\n";
	else cout << ans << "\n";
	return 0;
}

  • 디버깅

    • 처음에 u->v 방문을 체크하는 배열과 정점 방문여부를 체크하는 배열 두가지를 사용하여 해결하고자 하였으나 WA가 나왔습니다.
    • 또한 BFS를 이용하여 구현했지만 테스트를 통과하지 못하였습니다. DFS로 대체하니 통과 되었는데 정확한 이유는 찾지 못했습니다.

  • 제출결과

    48ms

3.마무리

  • 플로이드-와샬과 같이 정형화된 알고리즘을 사용할 줄 아는 것도 중요하지만, dfs를 응용하여 충분히 구현가능하고 삼성역량테스트를 볼 때 더 도움이 될 것입니다.
 BOJ

Related Posts