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

[문제]

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD&categoryId=AV14geLqABQCFAYD&categoryType=CODE

SW Expert Academy

[풀이]

bfs로 0부터 시작하여 99에 도달할 수 있는지를 구하였다.

※테스트케이스마다 길을 저장해 놓은 벡터 v를 clear해줘야 함!

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>//memset
using namespace std;

int T, N;
vector<int>v[100];
bool visited[100];

int bfs() {
	queue<int>q;
	q.push(0);
	visited[0] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (x == 99)
			return 1;
		int vSize = v[x].size();
		for (int i = 0; i < vSize; i++) {
			int nx = v[x][i];
			if (visited[nx] == false) {
				visited[nx] = true;
				q.push(nx);
			}
		}
	}
	return 0;
}

void solution() {
	int testcase;
	for (int t = 1; t <= 10; t++) {
		cin >> testcase >> N;
		memset(visited, false, sizeof(visited));
		int a, b;
		for (int i = 0; i < N; i++) {
			cin >> a >> b;
			v[a].push_back(b);
		}
		cout << '#' << testcase << ' ' << bfs() << '\n';
		for (int i = 0; i < 100; i++) {
			v[i].clear();
		}
	}
}

int main() {
	solution();
	return 0;
}