(백준/c++) 11403 - 경로찾기 / BFS, 그래프

 

"(백준/c++) 11403 - 경로찾기 / BFS, 그래프"

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

 

---

 

🏆 solved.ac 난이도: 실버1

 

오늘 쉬는 날이라 문제 푸는게 재미있다.

Array 변수 이름은 Floyed이지만? 플로이드 와샬보다 BFS를 사용해서 푸는게 더 편할거 같아서 BFS로 풀었다. 

다른 BFS와 다른 점은 모든 점에서 방문을 초기화 시켜줘야한다. 

ex ) 1 -> 5 -> 6 -> 7  이런 연결이 있을 때, 1을 5, 6, 7을 모두 방문 할 수 있다는 표시를 해줘야하고 그 다음 5번, 6번, 7번점도 이전에 방문 했더라도 연결되었는지 확인하기 위해 점 시작점에서 방문을 초기화 해야한다. 

#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;

vector<int> arr[101]; 
int Floyed[101][101] = {0, };
bool visit[101] = { false, };
queue<int> que;

int main(void)
{
	int N; cin >> N; 

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int a; 
			cin >> a; 

			if (a)
			{
				arr[i].push_back(j); 
			}
		}
	}

	//=============================================//

	for (int i = 1; i <= N; ++i)
	{
		memset(visit, false, sizeof(visit));

		if (visit[i])
		{
			continue;
		}

		que.push(i);
		visit[i] = true;

		while (!que.empty())
		{
			int temp = que.front();
			visit[temp] = true;
			que.pop();

			for (int j = 0; j < arr[temp].size(); ++j)
			{
				if (visit[arr[temp][j]] == false)
				{
					visit[arr[temp][j]] = true;
					Floyed[i][arr[temp][j]] = 1;
					que.push(arr[temp][j]);
				}
				else if(visit[arr[temp][j]] == true && arr[temp][j] == i)
				{
					Floyed[i][i] = 1;
				}
			}
		}
	}


	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cout << Floyed[i][j] << " ";
		}
		cout << endl; 
	}
	return 0; 
}