[백준 11403번] [DFS] 경로 찾기

Approach

처음에는 DFS를 돌 되, 스택을 활용해서 자신보다 밑에 있는 element 들은 방문할 수 있다는 점을 활용해서 component별로 처리하려고 했는데 사이클이 존재할 수 있는 측면때문에 실패하였다. 물론 코드를 잘(?) 짜면 가능할 것 같기도 하다.

 

기본적인 접근 방법은 모든 노드들에 대해서 dfs를 돌면서, 방문할 수 있는 노드를 찾아나가면 된다.

다만, 유의할 지점이 사이클이 존재할 수 있기 때문에 자기 자신으로 돌아오는 간선이 있으면 따로 체크해주어야 한다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int r[100][100];
int result[100][100];
int visited[100];
int n;
vector<int> v;
int cur;
bool flag;

void dfs(int x){
    visited[x] = 1;
    v.push_back(x);
    for(int i = 0; i < n; i++){
        if(!visited[i] && r[x][i] == 1) dfs(i);
        if(r[x][i] == 1 && i == cur) flag = true;
    }

    return;
}

int main(void){
    fastio;
    memset(result, 0, sizeof(result));
    memset(visited, 0, sizeof(visited));

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

    for(int i = 0; i < n; i++){
        v.clear();
        memset(visited, 0, sizeof(visited));
        cur = i;
        flag = false;
        dfs(i);
        if(flag) result[i][i] = 1;
        for(int j = 1; j < v.size(); j++){
            result[i][v[j]] = 1;
        }       
    }

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