[백준 알고리즘]/[C++]
2644번 촌수계산 | BFS | Baekjoon BOJ 백준 2644 C++ 코드, 해설, 풀이
말하는펭귄
2021. 2. 9. 18:35
728x90
반응형
이번 포스팅은 백준 2644번 촌수계산입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진
www.acmicpc.net
기본 알고리즘
BFS 너비 우선 탐색
전체 코드
|
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
|
//백준2644 촌수계산
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 100;
int n;
int a, b;
int map[MAX][MAX] = { 0, };
bool visited[MAX] = { 0, };
int depth[MAX] = { 0, };
queue<int> q;
void BFS(int v) {
q.push(v);
visited[v] = true;
while (!q.empty()) {
v = q.front();
q.pop();
for (int w = 1; w <= n; w++) {
if (map[v][w] == 1 && visited[w] == 0) {
q.push(w);
visited[w] = true;
depth[w] = depth[v] + 1;
}
}
}
}
int main() {
cin >> n;
cin >> a >> b;
int m;
cin >> m;
while (m--) {
int x, y;
cin >> x >> y;
map[x][y] = 1;
map[y][x] = 1;
}
BFS(a);
if (depth[b] == 0)
cout << -1;
else
cout << depth[b];
}
|
cs |
728x90
반응형