BaekJoon 11403번: 경로 찾기(C++)

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

11403번: 경로 찾기

풀이법

1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다.

2) 각 행 별로 방문한 곳을 체크하는 visited배열을 초기화 해준 후 현재 갈 수 있는 값이 1인 경우를 확인하여, BFS기반의 알고리즘으로 탐색을 하여, 방문 가능한 node들을 visited배열에 담아 주었다. 

3) 이후 makeArr2 함수를 통해 visited배열이 true인 곳들을 최종 답이 될 Arr2에 넣어줌으로써 문제를 해결할 수 있었다.

4) 문제를 명확하게 이해하기 위해서 손으로 개요를 잡았던 것이 더 빠르게 문제를 해결할 수 있던 원인이자 이유였던 것 같다. 

 

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int n;
int arr[101][101];
int arr2[101][101];
bool visited[101];
void clearVisited()
{
	for (int i = 1; i <= n; i++)
	{
		visited[i] = false;
	}
}
void checkpath(int a, int b)
{
	visited[b] = true;
	queue<pair<int, int>> q;
	q.push({ a,b });
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();

		for (int i = 1; i <= n; i++)
		{
			if (arr[nowY][i] == 1 && !visited[i])
			{
				visited[i] = true;
				q.push({ nowY,i });
			}
		}
	}
}
void makeArr2(int x)//행
{
	for (int i = 1; i <= n; i++)
	{
		if (visited[i] == true)
		{
			arr2[x][i] = 1;
		}
		else
			arr2[x][i] = 0;
	}
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> arr[i][j];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		clearVisited();
		for (int j = 1; j <= n; j++)
		{
			if (arr[i][j] == 1)
			{
				checkpath(i, j);
			}
		}
		makeArr2(i);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << arr2[i][j] << " ";
		}
		cout << "\n";
	}
}