Easy is Perfect

[백준] 11403번 C/C++ 풀이 _ 경로찾기

  • melonicedlatte
  • Aug 26, 2018


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

경로 찾기 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB129356585471150.320%

문제

가중치 없는 방향 그래프 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으로 출력해야 한다.

예제 입력 1 

3
0 1 0
0 0 1
1 0 0

예제 출력 1 

1 1 1
1 1 1
1 1 1

예제 입력 2 

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

예제 출력 2 

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 를 이용하여 풀었습니다.
각 노드에서 갈 수 있는 노드를 스택에 계속 넣어주고 is_visited 배열에 표시한 다음에 stack 에 더 이상 원소가 없을 때까지 dfs 를 반복해줍니다. 

dfs 를 다 끝내고 나면, 방문한 노드를 갱신해줍니다.
각 노드에 관해서 모두 수행하면 문제가 해결됩니다. 


혹은 bfs 나 아래의 링크에서 처럼 플로이드-와샬 알고리즘을 이용하여 해결할 수 있습니다. 

http://gnujoow.github.io/boj/2016/09/08/BOJ5-11403/ 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <stack>
#define N_MAX 100 + 1
using namespace std;
 
void dfs(int _node[N_MAX][N_MAX], int _start_node, int _N) {
    int is_visited[N_MAX] = { 0 };
    stack<int> dfs_stack;
    dfs_stack.push(_start_node);
    while (dfs_stack.size()) {
        int now_node = dfs_stack.top();
        dfs_stack.pop();
 
        // 배열 돌면서 해당 노드에 연결되고 방문되지 않은 경우에 stack 에 넣어준다. 
        for (int to_node = 0; to_node < _N; to_node++) {
            if (_node[now_node][to_node] && is_visited[to_node] == 0) {
                dfs_stack.push(to_node);
                is_visited[to_node] = 1;
            }
        }
    }
 
    // is_visited를 보고 갱신한다. 
    for (int n_idx = 0; n_idx < _N; n_idx++)
        if(is_visited[n_idx]) 
            _node[_start_node][n_idx] = 1;
 
    return ; 
}
 
int main() {
    int N;
    int root[N_MAX][N_MAX];
    cin >> N;
    // input 
    for (int r_idx = 0; r_idx < N; r_idx++)
        for (int c_idx = 0; c_idx < N; c_idx++)
            cin >> root[r_idx][c_idx];
 
    // dfs
    for (int node = 0; node < N; node++) 
        dfs(root, node, N);
 
    // print
    for (int r_idx = 0; r_idx < N; r_idx++){
        for (int c_idx = 0; c_idx < N; c_idx++){
            cout << root[r_idx][c_idx] << " ";
        }
        cout <<  "\n";
    }
 
    return 0; 
}
cs



Search