[11403] 경로 찾기

풀이

입접 행렬을 입접 리스트로 바꿔서 저장합니다. 그리고 x에서 y까지 가는 경로를 찾습니다. q에 x를 먼저 넣고 v[x]의 값들 중 y의 값과 같은 것이 있으면 찾은 것이고, 끝까지 못찾으면 x에서 y까지가는 경로가 없는 것입니다.

코드

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 100
vector< vector<int> > v(100, vector<int>(0,0));
int bfs(int x, int y, int n) {
	queue<int> q;
	bool check[MAX + 1][MAX + 1];//[i][j] : i에서 j로 가는 에지를 지났는지
	for (int i = 0; i < n; i++) {
		memset(check[i], false, sizeof(check[i]));
	}
	q.push(x);
	int curr = 0, next = 0;
	while (!q.empty()) {
		curr = q.front(); q.pop();
		for (int k = 0; k < v[curr].size(); k++) {
			next = v[curr][k];
			if (next == y) return 1;
			if (check[curr][next] == false) {
				check[curr][next] = true;
				q.push(next);
			}
		}
	}
	return 0;
}
int main(void) {
	int n = 0, t=0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &t);
			if (t == 1) {
				v[i].push_back(j);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d ", bfs(i, j, n));
		}
		printf("\n");
	}
	return 0;
}