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

11403번: 경로 찾기 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	256MB	27377	15022	10648	54.130%

 

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

 

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

 

예제 입력

3
0 1 0
0 0 1
1 0 0

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

예제 출력

1 1 1
1 1 1
1 1 1

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

풀이

백준에서는 플로이드-와샬 알고리즘으로 분류하였지만 간단한 dfs알고리즘으로도 해결할 수 있는 문제여서 저는 dfs알고리즘을 활용하였습니다.

가중치가 없는 그래프이니 입력을 받을 때부터 입력값이 0이면 무시하고 1일때 해당 그래프의 정점을 벡터에 pushback했습니다.

예제입력 2를 기준으로

와 같이 데이터가 들어갑니다.

그 후에는 각 정점을 한번씩 탐색하여 간단한 dfs알고리즘을 이용해 visit배열에 들어간 값을 매번 출력했습니다.

동작 과정은 GIF 파일을 만들어 보았으며 0번정점을 시작으로 하는 예시를 들었습니다.

처음 만들어본 gif이미지라 미흡한 점이 많습니다ㅠㅠ 추후 개선해보겠습니다.

코드

// 경로 탐색
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<int>v[100];
int visit[100];
void dfs(int x){
    for(int i=0;i<v[x].size();i++){
        if(!visit[v[x][i]]){
            visit[v[x][i]]=1;
            dfs(v[x][i]);
        }
    }
}
int main(){
    int n,a;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a;
            if(a)v[i].push_back(j);
        }
    }
    for(int i=0;i<n;i++){
        memset(visit,0,sizeof(visit));
        dfs(i);
        for(int j=0;j<n;j++)
            cout<<visit[j]<<" ";
        cout<<"\n";
    }
}

11403번: 경로 찾기 (acmicpc.net)

11403번: 경로 찾기