경로 찾기

---

문제

graph에서 간선을 알려주고, i에서j로 갈수 있는지 인접행렬로 표현하는것이다.

---

여기서는 bfs로 풀었다. 예를들어
1. i번째 줄에서, board[i][j]==1를 찾아 그 요소를 q.push(j)한다.
2. q의 원소를 한개씩 꺼내서, board[i][j] !=1이라면, q.push(j)한다.
3. q.empty()가 true일때 까지 반복

---

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>

using namespace std;
#define endl "\n"

#define MAX 100+1
int n;
int board[MAX][MAX];
queue<int> q;

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> board[i][j];
		}
	}
}
void bfs() {

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (board[i][j]==1)
			{
				q.push(j);
			}
		}

		while (!q.empty())
		{
			int f = q.front();
			q.pop();

			for (int j = 1; j <= n; j++)
			{
				if (board[f][j]==1 && board[i][j] !=1)
				{
					board[i][j] = 1;
					q.push(j);
				}
			}
		}
	}
}

int main()
{
	input();
	bfs();

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << board[i][j] << ' ';
		}
		cout << endl;
	}
}