11403번: 경로 찾기

문제링크

C++

#include <iostream>
#include <cstring>

using namespace std;

int N;

int matrix[101][101];

int ret[101][101];

int visited[101];

void dfs(int start, int nod){
    if (visited[nod] == 1)
        return ;
    visited[nod] = 1;
    for (int i = 1; i <= N; i++){
        if (matrix[nod][i] == 1){
            if (nod != i){
                ret[start][i] = 1;
                dfs(start, i);
            }
        }
    }
}

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 >> matrix[i][j];
        }
    }

    for (int i = 1; i <= N; i++){
        memset(visited, 0, sizeof(int) * 101);
        dfs(i, i);
    }

    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            cout << ret[i][j] << " ";
        }
        cout << "\n";
    }

}

• BFS/DFS으로 각 정점마다 도달 가능 여부를 체크하는 방식을 사용했다
• 각 정점에서 $O(N^{2})$ 소요
• 모든 정점에 대해 BFS 실행시 총 $O(N^{3})$ 소요
  • 노드의 수가 늘어나는 경우 '플로이드-워셜 알고리즘'을 사용해야 할 것 같다 -> 학습 필요