C++ 백준 11403 경로 찾기

백푼 11403

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

11403번: 경로 찾기

풀이 전 나의 생각

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서,

i에서 j로 갈 수 있는지 확인해야 한다.

 

조건

- N (1 ≤ N ≤ 100)

 

과정

문제에서 요구하는 사항을 보면 i에서 j로 가는 길이가 양수인 경로가 있는지 없는지

구하라고 한다. 이 말은 결국 i에서 j로 갈 수 있는지 없는지 물어보는 것이다.

 

예를 들어, 노드 1에서 노드 3으로 갈 수 있는지 확인하려고 할 때,

주어진 방향의 간선을 따라 도착할 수 있는지 확인해주면 된다.

 

조금 더 이해를 돕자면, 문제에서 주어진 예제 입력1을 봤을 때

(0, 1) 부분이 1로 표시되어 있는 것을 볼 수 있다.

이는 0 -> 1의 방향이 있는 간선 정보가 주어진 것이다.

 

이 문제의 풀이 방법으로는 플로이드 - 워셜 알고리즘과 BFS, DFS 탐색이 있다.

그중에서도 플로이드 - 워셜 알고리즘을 사용하면 간단하게 풀 수 있다. 

하지만 BFS, DFS로 푸는 법을 알고 있어야 그래프에 대한 이해도가 높아질 것이라고

판단해서 BFS로 풀이를 진행했다.

 

BFS의 간략한 풀이과정은 다음과 같다.

1. 간선의 정보를 저장한다.

2. 0부터 N - 1까지 BFS탐색을 진행한다.

3. BFS에 진입한 시작 노드가 갈 수 있는 모든 노드를 1로 체크해준다.

 

1. 간선의 정보를 저장한다.

for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int node;
			cin >> node;

			if (node == 1)
			{
				G[i].push_back(j);
			}
		}
	}

 

2.  BFS에 진입한 시작 노드가 갈 수 있는 모든 노드를 1로 체크해준다.

void bfs(int st)
{
	fill(visited, visited + 101, false);

	queue<int> q;
	visited[st] = true;
	q.push(st);

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

		for (int next : G[now])
		{
			if (!visited[next] || next == st)
			{
				ans[st][next] = 1;
				visited[next] = true;
				q.push(next);
			}
		}
	}
}

0 -> 1, 1 -> 2, 2 -> 0 의 그래프가 있고 0이 시작 노드라고 가정할 때, 0은 방문 표시가 true가 되버려서

2 -> 0으로 가지 못하는 문제가 발생한다.

 

따라서 next == st (다음 노드가 시작 노드와 같다면) 조건을 추가하여 시작 노드까지 탐색할 수 있게 해준다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>> G(101);
int ans[101][101];
bool visited[101];

void bfs(int st)
{
	fill(visited, visited + 101, false);

	queue<int> q;
	visited[st] = true;
	q.push(st);

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

		for (int next : G[now])
		{
			if (!visited[next] || next == st)
			{
				ans[st][next] = 1;
				visited[next] = true;
				q.push(next);
			}
		}
	}
}

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

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int node;
			cin >> node;

			if (node == 1)
			{
				G[i].push_back(j);
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		bfs(i);
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << ans[i][j] << " ";
		}
		cout << '\n';
	}
}