[DFS] 백준 11403번 - 경로 찾기 (정답률 51%)

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

11403번: 경로 찾기

백준 DFS 연습 문제이다.

최근 문제풀면서 DFS에 대한 응용력이 부족한것같아 풀어보았다.

원리와 성격을 알지만 응용을 잘 할 수 있게 지속적으로 연습하자.

 

이 문제는 각 정점에서 다른 정점으로 갈 수 있는 경로가 있다면 1, 아니면 0을 N x N 행렬에 저장해 출력하라는 문제다. 모든 정점 쌍에 대해 dfs 탐색을 하면 시간 초과가 뜨지만, 한 정점에서 갈 수 있는 모든 점들을 찾으면 그 점들에 갈 수 있는 경로가 있다는 뜻이므로 실제로 dfs 탐색을 N^2 할 필요가 없이 N 개의 정점을 시작점으로 하여 dfs 탐색을 하면 된다.

 

아래는 소스코드. (4ms)

#include <iostream>
#define maxlen 101
using namespace std;
int N;
int Dir_Graph[maxlen][maxlen];
bool check[maxlen];
int Answer[maxlen][maxlen];
int SV;
// 점은 1~100 인덱스 유효.
 
void falsing(){
    for (int i = 1; i <= N; i++)
        check[i] = false;
}
 
void toAnswer(){
    for (int i = 1; i <= N; i++){
        if (check[i])
            Answer[SV][i] = 1;
        else
            Answer[SV][i] = 0;
        check[i] = false;
    }
}
 
void dfs(int curpos){
    for (int i = 1; i <= N; i++){
        if (!check[i] && Dir_Graph[curpos][i]){
            check[i] = true;
            dfs(i);
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            cin >> Dir_Graph[i][j];
        }
    }
    falsing();
    // 각 행별로 시작정점을 잡고, 그 정점에서 dfs탐색을 해서 갈 수 있었던 점들 모두 true.
    for (int start_virtex = 1; start_virtex <= N; start_virtex++){
        SV = start_virtex;
        dfs(SV);
        toAnswer();
        for (int i = 1; i <= N; i++)
            cout << Answer[start_virtex][i] << " ";
        cout << '\n';
    }
    return 0;
}