n명이 있고 m개의 간선이 주어졌을 때 s,e의 촌수를 계산한다. n<=100이라 간선은 배열로 만들고 dfs로 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 | #include <stdio.h> #include <queue> using namespace std; int main() { int n, a[101][101] = { 0, }, s, e, m, d[101] = { 0, }; scanf("%d%d%d%d", &n, &s, &e, &m); while (m--) { int u, v; scanf("%d%d", &u, &v); a[u][v] = a[v][u] = 1; } queue<int> q; q.push(s); d[s] = 1; while (q.size()) { int x = q.front(); q.pop(); if (x == e) { printf("%d", d[x] - 1); return 0; } for (int i = 1; i <= n; i++) { if (!a[x][i] || d[i]) continue; d[i] = d[x] + 1; q.push(i); } } printf("-1"); return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 10026 적록색약 (0) | 2017.09.01 |
|---|---|
| 6603 로또 (0) | 2017.09.01 |
| 2778 측량사 지윤 (0) | 2017.09.01 |
| 2917 늑대 사냥꾼 (1) | 2017.08.31 |
| 3372 보드 점프 (0) | 2017.08.31 |