[백준] 11403 경로 찾기 - 그래프, DFS

[ 문제링크 ]

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

 

🚩 조건

1. 가중치 없는 방향 그래프 G가 주어짐
2. (i,j)에 대해, i에서 j로 가는 길이가 양수인 경로가 있는지 구해라
3. 경로가 있으면 1, 없으면 0으로 + 인접행렬 형식으로 출력 

 

 

🚩 접근

• 그래프 -> vector로 구현
• 재귀적으로 구현하자 (ex. 4번 갈 수 있으면 4번이 갈 수 있는 1,2번도 갈 수 있고 1,2번이 갈 수 있는 ...)
  근데 이걸 어떻게 구현하지? 재귀의 탈출 조건을 모르겠다

 

 

🚩 시행착오

• vector<int> vec[100] != vector<vector<int>> vec; 

vector<int> v1[100];		//vector<int> 100개를 가지는 배열
v1[0].push_back(1);

vector<vector <int>> v2;	//vector<int>를 요소로 가지는 가변적인 배열
v2.push_back(vector<int>());	//처음에는 빈 배열이기 때문에 반드시 필요
v2[0].push_back(1);

• 재귀적으로 구현 = DFS
  
  • DFS에 대해서 좀 더 공부하자 ([참고] https://m42-orion.tistory.com/63)

(1) DFS 코드 (2) 0번 노드에 대한 DFS 과정

 

 

💻 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> vec;
vector<int> temp;
int visit[101];

void dfs(int x){
    for(int i=0;i<vec[x].size();i++){
        if(!visit[vec[x][i]]){
            visit[vec[x][i]]=1;
            dfs(vec[x][i]);
        }
    }
}

void print(int k){
    for(int i=0;i<k;i++){
        cout<<visit[i]<<" ";
    }
    cout<<"\n";
}

void clean(int k){
    for(int i=0;i<k;i++){
        visit[i]=0;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, x;
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>x;
            if(x==1) temp.push_back(j);
        }
        vec.push_back(temp);
        temp.clear();
    }
    
    for(int i=0;i<N;i++){
        dfs(i);
        
        print(N);
        clean(N);
    }
}