[백준] 경로 찾기 c++

 

경로 찾기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

54208

34020

25304

62.637%

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

---

플로이드 워셜 알고리즘을 이용해 문제를 해결한다.

알고리즘에서 i와k 그리고 k와 j가 서로 연결되어 있다면 i와 j도 연결됐다고 설정한다.

 

#include <iostream>

using namespace std;

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

	int N; // 노드의 수
	long mDistance[101][101]; // 2차원 배열을 선언, 최대 101개의 노드에 대한 거리 정보

	cin >> N; 

	// 입력받은 인접 행렬을 mDistance에 저장
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> mDistance[i][j]; // mDistance[i][j]는 i와 j 사이에 경로가 있으면 1, 없으면 0
		}
	}

	// 플로이드 워셜 알고리즘을 이용하여 모든 노드 간 경로를 계산
	for (int k = 0; k < N; k++) // 중간 경유지로 고려할 노드 k
	{
		for (int i = 0; i < N; i++) // 출발 노드 i
		{
			for (int j = 0; j < N; j++) // 도착 노드 j
			{
				// 경로 i -> k, k -> j가 존재하면 i -> j도 연결된 것으로 간주
				if (mDistance[i][k] == 1 && mDistance[k][j] == 1)
				{
					mDistance[i][j] = 1; // i에서 j로 가는 경로가 존재한다는 의미로 1로 설정
				}
			}
		}
	}


	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << mDistance[i][j] << " ";
		}
		cout << "\n"; 
	}
}

 

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