경로 찾기 (feat. 백준, 11403번)

경로 찾기
https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
set<int> arr[100];
bool visit[100];
int bfs(register int i, register int j){
    memset(visit, false, sizeof(visit));
    queue<int> q;
    q.push(i);
    visit[i] = true;
    while(!q.empty()){
        i = q.front(); q.pop();
        if(find(arr[i].begin(), arr[i].end(), j) != arr[i].end())
            return 1;
        for(auto iter = arr[i].begin(); iter != arr[i].end(); ++iter)
            if(!visit[*iter])
                visit[*iter] = true, q.push(*iter);
    }
    return 0;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N;
    cin >> N;
    for(register int i = 0, j, v; i < N; ++i)
        for(j = 0; j < N; ++j){
            cin >> v;
            if(v == 1)
                arr[i].insert(j);
        }
    for(register int i = 0, j; i < N; ++i){
        for(j = 0; j < N; ++j)
            cout << bfs(i, j) << " ";
        cout << "\n";
    }
	return 0;
}
// *&)*@*

 

반응형

1. i - j 가 연결되었는지를 찾는 문제입니다.
2. i - a - b - k - j 라면 i - j 가 연결되었다고 할 수 있습니다.
3. 따라서 i와 연결된 a, a와 연결된 b, b와 연결된 k 를 계속해서 탐색하여 최종적으로 j가 나오는지 확인하면 됩니다.