백준/11403/플로이드-와샬/경로 찾기

백준/11403/플로이드-와샬/경로 찾기

문제 해석

인접 행렬에서 i점에서 j점으로 갈 수 있는 길(즉, 다른 점을 통해 갈 수 있는지)이 있는지를 확인하는 문제입니다.

문제 풀이

i점에서 j점까지 각 점(0~N-1)을 사이에 두고 통과 할 수 있는 길인지를 확인하였습니다.

이 때 i->(다른 점), (다른 점)->j 두 개의 길이 모두 길이 있다면 i->j로 가는게 가능해지기 때문에, 이 둘의 길이 있는지에 대한 여부를 확인하면 됩니다.

for (int z = 0;z < N;z++)
{
	for (int y = 0;y < N;y++)
	{
		for (int x = 0;x < N;x++)
		{
			// y x사이의 통하는 길이 있다면 yx는 길을 가지고 있다는 뜻
			if ((arr[y][z] == 1) && (arr[z][x] == 1))
			{
				arr[y][x] = 1;
			}
		}
	}
}

자연 스럽게 다른 점을 통과한 길도 양수가 되면서 해당 점을 통해서도 다른 점으로 이동할 있는지를 판별할 수 있게 됩니다.

풀이

첫번째 풀이

#include<iostream>
using namespace std;

int arr[101][101];

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

	// 정점의 개수
	int N = 0;
	cin >> N;

	for (int y = 0;y < N;y++)
	{
		for (int x = 0;x < N;x++)
		{
			cin >> arr[y][x];
		}
	}

	for (int z = 0;z < N;z++)
	{
		for (int y = 0;y < N;y++)
		{
			for (int x = 0;x < N;x++)
			{
				// y x사이의 통하는 길이 있다면 yx는 길을 가지고 있다는 뜻
				if ((arr[y][z] == 1) && (arr[z][x] == 1))
				{
					arr[y][x] = 1;
				}
			}
		}
	}

	for (int y = 0;y < N;y++)
	{
		for (int x = 0;x < N;x++)
		{
			cout << arr[y][x] << ' ';
		}
		cout << '\n';
	}


	return 0;
}