728x90
문제
https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제 해결
1. DFS를 이용하여 1~N까지의 숫자를 탐색한다.
2. ex) 1에 대하여 탐색한다면 1에 대하여 깊이 탐색한 후 지나는 모든 노드들을 visit 한다.
3. visit이 true이면 map [1][j] = 1로 인접 행렬을 만든다.
코드
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
|
#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();
}
|
cs |
728x90
'c++ 백준 문제 풀이' 카테고리의 다른 글
[백준/C++][오큰수(17298번)] (0) | 2020.12.15 |
---|---|
[백준/C++][순열 사이클(10451번)] (0) | 2020.12.02 |
[백준/C++][(1761번)정점들의 거리] (0) | 2020.11.19 |
[백준/C++][(1197번)최소 스패닝 트리] (0) | 2020.11.19 |
[백준/C++][(1922번) 네트워크 연결] (0) | 2020.11.19 |