[BOJ]백준 11403번: 경로 찾기

BFS 혹은 DFS 입문자가 풀면 좋을 기초 문제

 

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

11403번: 경로 찾기

방향 그래프가 주어졌을 때, 임의의 정점 (i,j)의 경로 조합을 인접행렬을 사용해서 출력하는 프로그램

 

bfs의 핵심은, ① 큐를 사용한다 ② 이동 가능하다면 바로 방문 체크

인데, BFS를 잘 모르는 초심자가 풀기 좋은 문제라고 생각한다.

#include <cstdio>
#include <queue>
#include <memory.h>
using namespace std;
int n;
bool g[101][101], visit[101];
queue<int> q;
bool bfs(int node, int d) {
	visit[node] = true;
	q.push(node);
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for(int i=0;i<n;i++)
			if (g[cur][i] && (!visit[i]||i==node)) {
				visit[i] = true;
				q.push(i);
				if (i == d) return true;
			}
	}
	return false;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)scanf("%d", &g[i][j]);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d ", bfs(i, j));
			memset(visit, false, sizeof(visit));
			while (!q.empty())q.pop();
		}
		printf("\n");
	}
	return 0;
}

단순 BFS를 구현하고, 임의의 i,j에 대해 이중 for문을 통해 경로가 존재하는지 검사한 다음 출력해주면 끝!