백준 C++ 11403

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

11403번: 경로 찾기

 

문제 정리

그래프 만들고 경로 찾으면 되는 문제

 

생각

dfs 써서 그래프 연결 유무 확인을 하자! 방문했으면 1, 안했으면 0 출력

 

코드

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

int N, M;
int graph[100][100];
bool visited[100];

void dfs(int start){
    
    for(int i=0 ; i<N ; i++){
        if(graph[start][i] && !visited[i]){
            visited[i] = true;
            dfs(i);
        }
    }
}

int main(){
    cin >> N;

    for(int i=0 ; i<N ; i++){
        for(int j=0 ; j<N ; j++){
            cin >> graph[i][j];
        }
    }
    
    for(int i=0 ; i<N ; i++){
        memset(visited, false, sizeof(visited));
        dfs(i);
        for(int j=0 ; j<N ; j++){
            if(visited[j]){
            cout << 1 << " ";
            }
            else{
            cout << 0 << " ";
            }
        }
        cout << "\n";
    }
}

- 가중치가 없는 그래프!

 

 

참고한 글 + gif 이해가 매우 굿

https://hunidev.tistory.com/43

[백준 BOJ 11403번] 경로 찾기 (C / C++ ) [dfs, 그래프이론]