<링크>
https://koitp.org/problem/SDS_TEST_TREASURE/read/
<소스코드>
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 66 67 68 | #include<stdio.h> #include<string.h> #include<queue> #include<vector> using namespace std; vector<int> adj[1001]; queue<int> q; int isVisited[1001]; int N,M,K; int bfs(); int main() { int T; scanf("%d",&T); for (int t = 1; t <= T; ++t) { for (int i = 0; i <= 1000; ++i) adj[i].clear(); q = queue<int>(); memset(isVisited, 0, sizeof(isVisited)); scanf("%d%d%d", &N, &M, &K); for (int i = 0; i < M; ++i) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(b); } int ans = bfs(); printf("#%d ", t); if (ans) printf("%d\n", ans); else printf("-1\n"); } } int bfs() { q.push(1); int depth = 0; while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; ++i) { int cur = q.front(); q.pop(); if (cur == N) return depth; int s = adj[cur].size(); for (int i = 0; i < s; ++i) { int to = adj[cur][i]; if (!isVisited[to]) { isVisited[to] = 1; q.push(to); } } } ++depth; if (depth > K) return 0; } return 0; } | cs |
<풀이>
BFS를 통해 목적지가 나오면 그 때의 depth가 답이다.
또한 depth가 K를 초과하면 더이상 탐색할 필요가 없고
모든 노드를 다 돌아봤음에도 목적지를 못찾으면 답은 -1이다.
'알고리즘 풀이 > BFS' 카테고리의 다른 글
| 백준 2251 물통 (0) | 2018.08.01 |
|---|---|
| 백준 1525 퍼즐 (0) | 2018.07.31 |
| 백준 9019 DSLR (0) | 2018.07.31 |
| 백준 1963 소수 경로 (2) | 2018.07.30 |
| 백준 1697 숨바꼭질 (1) | 2018.07.29 |