문제 링크 : https://www.acmicpc.net/problem/6118
6118번: 숨바꼭질
문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재석이는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자. 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1<= M <= 50,000)개의 양방향 길로 이어져 있고, 그 양 끝을 A_i 와 B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)로 나타낸
www.acmicpc.net
수혀니가 있는 1번 헛간으로부터 가장 먼 헛간들의 갯수, 거리를 구하는 문제입니다.
간선 가중치가 없고 모든 최장거리를 전부 구해야되기 때문에 BFS를 사용하면 쉽게 해결할 수 있습니다.
한가지 주의할 점은 N이 최대 20,000 이기 때문에 O(N^2)인 인접행렬을 이용할 경우 시간초과가 납니다.
인접리스트 BFS를 돌면서 최대 거리, 최대 거리의 갯수, 재서기가 숨은 가장 작은 헛간을 찾아주시면 됩니다.
'알고리즘 문제 > 백준' 카테고리의 다른 글
| 백준 2811번. 상범이의 우울 (Java) (0) | 2019.07.14 |
|---|---|
| 백준 17284번. Vending Machine (Java) (0) | 2019.07.14 |
| 백준 1620번. 나는야 포켓몬 마스터 이다솜 (Java) (0) | 2019.03.22 |
| 백준 1697번. 숨바꼭질 (Java) (0) | 2019.03.22 |
| 백준 1238번. 파티 (Java) (0) | 2019.03.02 |