백준 11403번: 경로 찾기

문제 링크 : https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

아이디어 : BFS

한 줄을 탐색하면서, 값이 1인 것인 정점을 기준으로 탐색함.

그래서 답으로 사용할 배열의 값을 1로 변경.

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

int N;

int nMap[101][101];
int nAns[101][101];
int nChecked[101][101];

queue<int> q;

void BFS(int y)
{
	q.push(y);
	while (!q.empty())
	{
		int cy = q.front();
		q.pop();

		for (int i = 1; i <= N; i++)
		{
			if (nMap[cy][i] == 1 && nChecked[cy][i] == 0)
			{
				nAns[y][i] = 1;
				nChecked[cy][i] = 1;
				q.push(i);
			}
		}
	}

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

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> nMap[i][j];
		}
	}

	for (int y = 1; y <= N; y++)
	{
		BFS(y);

		memset(nChecked, 0, sizeof(nChecked));
	}

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

	return 0;
}

 

의견 : 처음에 문제 뜻을 이해 못했음. 그래서 출력 결과 또한 이해 못했음.