[백준/C++][경로 찾기(11403번)]

문제

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

11403번: 경로 찾기

문제 해결 

1. DFS를 이용하여 1~N까지의 숫자를 탐색한다.

2. ex) 1에 대하여 탐색한다면 1에 대하여 깊이 탐색한 후 지나는 모든 노드들을 visit 한다.

3. visit이 true이면 map [1][j] = 1로 인접 행렬을 만든다. 

 

코드

#include <iostream>
#include <cstring>
using namespace std;
int N;
int map[101][101];
bool visit[101] = {false};
void print(void){
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }    
}
void DFS(int node){
    for(int i = 0;i<N;i++){
        if(map[node][i] == 1 && !visit[i]){
            visit[i] = true;
            DFS(i);
        }
    }
}
int main(void){
    cin >> N;
    for(int i = 0;i<N;i++){
        for(int j =0;j<N;j++){
            cin >> map[i][j];
        }
    }
    
    for(int i = 0;i<N;i++){
        memset(visit,false,sizeof(visit));
        DFS(i);
        for(int j = 0;j<N;j++){
            if(visit[j]){map[i][j] = 1;}
        }
    }
    print();
}