[C++] 백준 11403: 경로 찾기

문제 이해

- 가중치 없는 방향 그래프 G가 주어진다.

- 모든 정점 (i, j)에 대하여 i에서 j로 가는 길이 있는지 없는지 구하라.

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 256MB

 

<입력>

- N: 정점의 개수 (1 ~ 100, 10^2)

- 인접 행렬(1일경우 경로가 존재, 0일경우 경로가 없음)

 

<출력>

- N개의 줄에 걸쳐 i에서 j로 가는 경로가 있으면 1, 없으면 0을 출력하라.

 

 

---

문제 풀이

처음에 생각한 풀이는

정점 i -> j로 가는 모든 경우의 수를 DFS로 해보는 풀이였다.

 

인접 행렬로 주어진 그래프를 벡터 배열을 통해 표현하고 DFS를 사용하였다.

 

단 i에서 다시 i로 가는 경우도 고려를 해야 했기에

처음 시작 정점을 방문 표시하지 않아야한다는 주의할 점이 있었다.

 

 

1. i - > j 모든 경우의 수 DFS

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

vector <int> map[105];
bool visited[105];
int ans[105][105];
bool flag;

void dfs(int start, int end, bool check){
    if(start == end && check){
        flag = true;
    }

    int size = map[start].size();
    for(int i = 0; i < size; i++){
        int next = map[start][i];
        if(!visited[next]){
            visited[next] = true;
            dfs(next, end, true);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int tmp;
            cin>>tmp;
            if(tmp == 1){
                map[i].push_back(j);
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            flag = false;
            memset(visited, 0, sizeof(visited));

            dfs(i, j, false);
            if(flag){
                ans[i][j] = 1;
            }
        }
    }

    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

 

 

그 다음에 더 나은 풀이가 없을까 인터넷을 찾아봤는데,

 

i에서 출발하는 경우의 수에 대하여 일일히 다 체크해볼 필요 없이

DFS 한 번 돌면 각 정점 j로 가는 경우의 수를 모두 파악할 수 있었다.

 

 

2. 시작하는 정점으로만 반복 DFS

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

vector <int> map[105];
bool visited[105];

void dfs(int start){

    int size = map[start].size();
    for(int i = 0; i < size; i++){
        int next = map[start][i];
        if(!visited[next]){
            visited[next] = true;
            dfs(next);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int tmp;
            cin>>tmp;
            if(tmp == 1){
                map[i].push_back(j);
            }
        }
    }

    for(int i = 1; i <= n; i++){
        memset(visited, 0, sizeof(visited));
        dfs(i);
        
        for(int j = 1; j <= n; j++){
            cout<<visited[j]<<" ";
        }
        cout<<"\n";
    }

    return 0;
}

 

 

위의 방법도 간단했지만

플로이드-워셜 알고리즘을 사용할 경우 더 쉽게 코드를 짤 수 있다.

이 문제에서 N이 100 이하로 O(N^3)의 시간 복잡도를 가져도 시간제한에 걸리지 않아 적용할 수 있다! 

 

 

플로이드-워셜 알고리즘은 원래 가중치가 더 작을경우 갱신하지만 이 문제는 경로가 존재하는지만 파악하는 문제였기에

중간 정점 k로 들어오고 나가는 경로가 존재할경우 초기화해주었다.

 

 

3. 플로이드-워셜 알고리즘

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

int adj[105][105];
int dist[105][105];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin>>adj[i][j];
        }
    }

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(adj[i][k] == 1 && adj[k][j] == 1){
                    adj[i][j] = 1;
                }
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout<<adj[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

 

 

---

배운 점

DFS 알고리즘의 결과의 의미에 대해서 다시 한 번 생각해볼 수 있는 문제였고,

플로이드-워셜 알고리즘의 기초에 대해 배울 수 있었다!