C++)
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX_NUM 101
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, a, b, m, x, y;
cin >> n;
cin >> a >> b;
vector<vector<int>> v(n + 1);
cin >> m;
for (int i = 0; i < m; i++) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
int visited[MAX_NUM];
fill(visited, visited + MAX_NUM, -1);
queue<int> q;
visited[a] = 0;
q.push(a);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < v[cur].size(); i++) {
int next = v[cur][i];
if (visited[next] == -1) {
visited[next] = visited[cur]+1;
if (next == b)
break;
q.push(next);
}
}
}
cout << visited[b];
return 0;
}
Python)
import sys
from collections import deque
read = sys.stdin.readline
n = int(read().rstrip())
a, b = map(int, read().rstrip().split())
m = int(read().rstrip())
arr = [ [] for _ in range(n+1)]
visited = [-1] * (n+1)
for _ in range(m):
x, y = map(int, read().rstrip().split())
arr[x].append(y)
arr[y].append(x)
q = deque()
visited[a] = 0
q.append(a)
while q:
cur = q.popleft()
for next in arr[cur]:
if visited[next] == -1:
visited[next] = visited[cur] + 1
if next == b:
break
q.append(next)
print(visited[b])'백준 2 > 그래프' 카테고리의 다른 글
| [백준 4963] 섬의 개수 (0) | 2020.12.08 |
|---|---|
| [백준 6593] 상범 빌딩 (C++) (0) | 2020.12.08 |
| [백준 10552] DOM (0) | 2020.12.08 |
| [백준 9466] 텀 프로젝트 (0) | 2020.12.08 |
| [백준 10026] 적록색약 (C++/Python) (0) | 2020.12.08 |