반응형
문제
https://www.acmicpc.net/problem/2644
풀이
A와 B 사이에 거리를 구하는 문제이다. 그래프 탐색인 bfs를 이용해서 A에서 B까지 거리를 구하면 된다. 만약 가는 경로가 없다면 -1을 리턴해주면 된다. bfs 탐색을 하면서 각 level이 끝날때마다 탐색 횟수를 증가시키면 된다. 탐색을 하다가 다음 방문할 정점이 B이면 탐색 횟수를 반환해준다.
코드
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
58
59
60
61
62
63
64
65
|
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int A, B;
int graph[101][101];
bool visit[101];
int n;
int bfs(int start)
{
visit[start] = true;
q.push(start);
bool find = false;
int result = 0;
while (!q.empty())
{
int len = q.size();
for (int i = 0; i < len; i++)
{
int cur = q.front(); q.pop();
for (int next = 1; next <= n; next++)
{
if (graph[cur][next] && !visit[next])
{
q.push(next);
visit[next] = true;
if (next == B) return result + 1;
}
}
}
result++;
}
return -1;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
cin >> A >> B;
int m;
cin >> m;
int x, y;
for (int i = 0; i < m; i++)
{
cin >> x >> y;
graph[x][y] = 1;
graph[y][x] = 1;
}
cout << bfs(A);
return 0;
}
|
cs |
반응형
'BOJ' 카테고리의 다른 글
백준 1700 - 멀티탭 스케줄링 (0) | 2019.06.03 |
---|---|
백준 2503 - 숫자 야구 (0) | 2019.06.01 |
백준 2193 - 이친수 (0) | 2019.05.26 |
백준 1473 - 음식물 피하기 (0) | 2019.05.23 |
백준 1012 - 유기농 배추 (0) | 2019.05.18 |