경로찾기

백준알고리즘

경로찾기

먼지의삶 2019. 9. 16. 23:08

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
54
55
56
57

#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int n;
int map[101][101];
int ans[101][101];
bool d[101];
 
void bfs(int x){
    queue<int> q;
    int node = x;
    for(int i = 1; i<= n; i++){
        if(map[x][i]== 1 &&d[i] == false) {
            q.push(i);
            d[i] = true;
            ans[node][i] = 1;
        }
    }
    while(!q.empty()){
        x = q.front(); q.pop();
        for(int i = 1; i<= n; i++){
            if(map[x][i] == 1 && d[i] == false){
                d[i] = true;
                ans[node][i] = 1;
                q.push(i);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin>>map[i][j];
 
        }
    }
    for(int i = 1; i<= n; i++){
        bfs(i);
        memset(d,false, sizeof(d));
    }
    for(int i = 1; i<= n; i++){
        for(int j = 1; j<= n; j++)
        {
            cout<<ans[i][j]<<' ';
        }cout<<'\n';
    }
 
    return 0;
 
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

 

정말정말 쉬운 BFS문제였다.

일단 크기가 굉장히 작은 최대 100x100 배열이기때문에 초기화 등등 여러가지 부담될만한 시간적 요소가

없었기 때문에, 간단하게 짤수있었다.