[BOJ 11403 / C++] 경로 찾기 (그래프)

문제링크: https://www.acmicpc.net/problem/11403

 

> 방법 1. 인접 행렬 (adjacent matrix)

1-1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    
    vector<vector<int>> adj(n, vector<int>(n));

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

    vector<vector<int>> path(n, vector<int>(n, 0));
    
    for (int st = 0; st < n; st++) {
        vector<int> vis(n, 0);
        queue<int> Q;

        Q.push(st);

        while (!Q.empty()) {
            int cur = Q.front(); Q.pop();
            for (int nxt = 0; nxt < n; nxt++) {
                if (adj[cur][nxt] == 1 && !vis[nxt]) {
                    vis[nxt] = 1;
                    Q.push(nxt);
                }
            }
        }
        
        path[st] = vis;
    }    

    for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << path[i][j] << ' ';
            }
            cout << '\n';
        }
}

 

 

1-2. 시간복잡도

인접행렬의 모든 정점을 탐색해야하므로 O(n^2)이 시간복잡도가 된다. n = 100이므로 시간제한 1초 안에 통과 가능하다.

 

 

1-3. 분석

인접행렬의 방식으로 그대로 진행한다. 처음에 정점은 0부터 n-1까지로 생각하고 st = 0 .. n-1까지 테스트해보며 vis를 할 수 있는지 없는지 확인한다. adj[cur][nxt] ==1로 갈 수 있는지 없는지 판단하면 된다.

 

 

> 방법 2. 인접 리스트 (adjacent list)

2-1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int edge;
            cin >> edge;
            if (edge == 1) adj[i].push_back(j);
        }
    }

    vector<vector<int>> path(n, vector<int>(n));

    for (int st = 0; st < n; st++) {
        vector<int> vis(n, 0);
         
        queue<int> Q;
        Q.push(st);

        while (!Q.empty()) {
            int cur = Q.front(); Q.pop();

            for (int nxt : adj[cur]) {
                if (vis[nxt]) continue;
                vis[nxt] = true;
                Q.push(nxt);
            }
        }

        path[st] = vis;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << path[i][j] << ' ';
        }
        cout << '\n';
    }
}

 

 

2-2. 시간복잡도

인접리스트로 하면 존재하는 edge만 검사하기 때문에 O(v+e)가된다. 여기서는 이론상 e = v^2 이므로 최악의 경우 시간복잡도는 인접행렬과 비슷하지만 좀 더 효율적이라고 볼 수 있다.

 

 

2-3. 분석

입력으로 인접행렬 형식으로 주어지는데 인접리스트가 더 익숙하고 시간복잡도의 이점도 있기 때문에 인접리스트로 변환해서 그래프 정보를 저장하고 있다가 bfs로 탐색하는 방식을 사용할 수도 있다. 두가지 방법 모두 가능한 방법이다.

 

플로이드 워셜의 방식으로도 이 문제는 해결 가능하다. k = st .. n으로 두고 다른 정점을 통해서도 해당 정점으로 이동할 수 있는지를 판단하는 방식으로 해결 가능하다.