1219. [S/W 문제해결 기본] 4일차 - 길찾기

방향그래프가 주어질 때(일방 통행이므로!) 0번에서 99번노드로 가는 길이 있는지 탐색하는 문제입니다.

단순히 길이 있는지없는지만 파악하면되므로 0번노드부터 전체탐색을하여 dfs함수의 매개변수v가 99이면 99번 노드까지 탐색을

한 것이므로 그 때 길이있다고 check하여 빠져나와 출력하면됩니다. 테스트케이스가 끝날 때마다 선언 해둔 배열만 초기화해주면됩니다.

자료구조책의 dfs개념파트를 보고 충분히 풀 수 있는 문제입니다.

코드

#include<iostream>
#include<cstring>
using namespace std;
int visited[100];
int graph[100][100];
void dfs(int v);
bool check;
int main()
{
	int t, v1, v2, edge;
	for (int i = 0; i < 10; i++)
	{
		memset(visited, 0, sizeof(visited));
		memset(graph, 0, sizeof(graph));
		check = false;
		cin >> t >> edge;
		for (int i = 0; i < edge; i++)
		{
			cin >> v1 >> v2;
			graph[v1][v2] = 1;
		}
		dfs(0);
		cout << "#" << t << " ";
		if (check)
			cout << 1;
		else
			cout << 0;
		cout << endl;
	}
}
void dfs(int v)
{
	visited[v] = 1;
	//99번쨰에 도달했으므로 길이 있는것임.
	if (v == 99)
	{
		check = true;
		return;
	}
	for (int i = 0; i < 100; i++)
	{
		if (!visited[i] && graph[v][i])
			dfs(i);
	}
}