BOJ 11403번 경로 찾기

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

github : https://github.com/junho0956/Algorithm/blob/master/11403/11403/%EC%86%8C%EC%8A%A4.cpp

 

문제는 DFS, BFS, FLOYD 3가지 알고리즘 중 1가지만 알고 계시면 해결가능합니다.

아래 코드는 DFS 로 구현한 코드입니다.

현재위치 [i,j] 가 1이면 i->j 가 가능한 것이므로 이에 대한 가능한 모든 정점을 방문하는 dfs를 구현하였습니다.

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int arr[101][101];
int ans[101][101];
int N;
vector<int> v[101];
bool visit[101];
 
void dfs(int s, int e, int m) {
    visit[e] = true;
    ans[m][e] = 1;
 
    for (int i = 1; i <= N; i++) {
        if (arr[e][i] && !visit[i]) dfs(e, i, m);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
            v[i].push_back(j);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j]) {
                memset(visit, 0, sizeof(visit));
                dfs(i, j, i);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << ans[i][j] << ' ';
        }
        cout << "\n";
    }
 
    return 0;
}