문제 출처

1. 문제설명

• N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.
• 간선은 양방향 또는 단방향으로 구성되어 있다.
  • 양방향은 1, 단방향은 0으로 입력된다.
• 어떤 정점에서 다른 정점으로 이동할 때 길이 없다면 단방향을 양방향으로 바꿔줘야 한다.

• 출발점과 도착점이 주어질 때 바꿔줘야 하는 횟수를 출력하라.

• 문제 분류
  • Graph, Floyd

2. 알고리즘 설계

• 플로이드-워셜 알고리즘 문제이다.
• 입력받기 전에 자기 자신으로 이동하는 경로의 비용은 0, 나머지는 INF로 채운다.
• 서로 다른 정점 간 비용이 중복되지 않으므로, 입력을 받을 때 단순 저장한다.
  • 그래프의 간선은 양방향 또는 단방향이다.
  • 즉, u->v는 비용이 0이고, v->u는 단방향이라면 비용이 1, 양방향이면 0이된다.
• 이제 플로이드를 통해 모든 최단 경로의 비용을 계산한다.
• 진행방향으로 경로가 없는 단방향 간선으로 이동했을 때의 값을 더해준다.
  • 플로이드 계산할 때 이미 더해진다.
• D[src][dest]를 출력하면 된다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f, SZ = 252;
int n, m, u, v, b, k;
int D[SZ][SZ];

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for(int i=1; i<=n; i++) {
		fill(D[i], D[i]+n+1, INF);
		D[i][i] = 0;
	}

	while(m--) {
		cin >> u >> v >> b;
		D[u][v] = 0;
		D[v][u] = !b;
	}

	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				D[i][j] = min(D[i][j], D[i][k]+D[k][j]);

	cin >> k;
	while(k--) {
		cin >> u >> v;
		cout << D[u][v] << '\n';
	}

	return 0;
}