[알고리즘] DFS 경로찾기

DFS 경로찾기 (백준 11403번)

 

 

n: 정점의 개수

모든 정점(i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구분.

방향이 있는 간선에 대한 문제를 풀기위해서는 destination을 기준으로 도달이 가능한지를 확인이 필요하며,

방문을 확인하기 위해 2차원 배열을 사용.

기존 DFS 알고리즘의 확인하는 부분은 동일하게 사용.

 

예제
3
0 1 0
0 0 1
1 0 0

#include <iostream>
#include <vector>
using namespace std;

bool graph[101][101];
bool visit[101][101];
int n;

void input()
{
	cin >> n;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			cin >> graph[i][j];
}

void output()
{
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
			cout << graph[i][j] << " ";
		cout << endl;
	}

}

void findRoute(int des, int y)
{
	graph[des][y] = true;
	visit[des][y] = true;
	for(int i=0; i<n; i++)
	{
		if( !visit[des][i] && graph[y][i] )
		{
			findRoute(des,i);
		}
	}
}

void DFS(void)
{
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			if( graph[i][j] && !visit[i][j] )
			{
				findRoute(i,j);
			}
		}
	}
}

int main()
{
	input();
	DFS();
	output();

	return 0;
}