백준 알고리즘 1956 (운동) - C++, Python

[문제] 백준 알고리즘 1956 (운동)

> https://www.acmicpc.net/problem/1956

1956번: 운동

가능한 사이클의 최소 이동 거리를 찾는 문제.

유의할 점은 도착이 끝나는 것이 아니라, 다시 제자리로 돌아오는 것.

1 -> 2 -> 1 이런 짧은 사이클도 가능하다. 경로가 없으면 -1 출력.

플로이드 와샬 알고리즘을 활용하면 된다. 

 

 

[문제 해결]

1. 2차원 graph를 INF(1e9)로 초기화한 후, 노드에 거리들을 저장해준다.

2. 플로이드 와샬 알고리즘 (모든 경로를 거쳐가는 경우를 고려한 알고리즘)

   - 거쳐가는 중간 노드 i, 시작 노드 v, 도착 노드 nv의 시간 복잡도 O(V^3)

   - i와 v가 같은 경우(시작=중간) 또는 i와 nv가 같은 경우(중간=도착)은 continue로 생략

   - 중간 노드를 거쳐가는 경우가 더 거리가 짧다면 갱신

3. graph에서 시작 노드와 도착 노드가 같은 idx의 값의 min값을 출력해준다.

   - min 값이 INF라면 -1 출력

 

 

[C++]

#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 401;
const int INF = 1e9;
int n, m;
int graph[MAX][MAX];

void print() {
	int _min = INF;
	for (int i = 1; i <= n; i++) {
		if (_min > graph[i][i]) _min = graph[i][i];
	}
	if (_min != INF) printf("%d\n", _min);
	else printf("-1\n");
}

void solve_fw() {
	for (int i = 1; i <= n; i++) {
		for (int v = 1; v <= n; v++) {
			if (v == i) continue;
			for (int nv = 1; nv <= n; nv++) {
				if (nv == i) continue;
				if (graph[v][nv] > graph[v][i] + graph[i][nv]) {
					graph[v][nv] = graph[v][i] + graph[i][nv];
				}
			}
		}
	}
	print();
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (graph[a][b] > c) graph[a][b] = c;
	}
	solve_fw();
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[1e9] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    if graph[a][b] > c:
        graph[a][b] = c

def answer():
    _min = 1e9
    for i in range(1, n+1):
        if _min > graph[i][i]:
            _min = graph[i][i]
    print(_min if _min != 1e9 else -1)
    return

def solve_fw():
    for i in range(1, n+1):
        for v in range(1, n+1):
            if i == v:
                continue
            for nv in range(1, n+1):
                if i == nv:
                    continue
                if graph[v][nv] > graph[v][i] + graph[i][nv]:
                    graph[v][nv] = graph[v][i] + graph[i][nv]
    answer()
    return

solve_fw()