백준 6118번 숨바꼭질 C++

백준 6118번 숨바꼭질 C++

출처 : https://www.acmicpc.net/problem/6118

bfs탐색을 이용하여 해결할 수 있는 문제이다.

2차원 벡터로 그래프를 나타내고 노드와 거리를 저장하도록 pair 를 이용하고 found벡터와 함께 bfs탐색을 하면서 문제를 해결하였다.

탐색을 하다가 거리가 갱신되면 답을 갱신하고 cnt를 0으로 초기화 해주고, 만약 거리가 같다면 기존 답과 비교해서 새로 찾은 헛간의 번호가 더 작다면 갱신해주고, cnt를 1 늘려주었다.

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; int node1, node2; vector> graph(n + 1, vector()); vector found(n + 1, false); for (int i = 0; i < m; i++) { cin >> node1 >> node2; graph[node1].push_back(node2); graph[node2].push_back(node1); } queue> q; q.push({ 1,0 }); found[1] = true; int ans = 1; int dist = 0; int cnt = 0; while (!q.empty()) { auto a = q.front(); q.pop(); if (a.second > dist) { cnt = 0; dist = a.second; ans = a.first; } if (a.second == dist) { cnt++; ans = min(ans, a.first); } for (int next : graph[a.first]) { if (found[next]) continue; found[next] = true; q.push({ next,a.second + 1 }); } } cout << ans << " " << dist << " " << cnt; };

from http://kjhcocomi.tistory.com/42 by ccl(A) rewrite - 2021-11-18 12:26:28