알고리즘/BOJ

백준 6118번 숨바꼭질

꾸준함. 2019. 9. 29. 04:50

문제 링크입니다: 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로 설정하였습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
const int MAX = 20000 + 1;
const int INF = 987654321;
int N, M;
vector<int> graph[MAX];
int dist[MAX];
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ 0, 1 });
for (int i = 2; i < MAX; i++)
{
dist[i] = INF;
}
while (!pq.empty())
{
int cost = pq.top().first;
int node = pq.top().second;
pq.pop();
if (dist[node] < cost)
{
continue;
}
for (int i = 0; i < graph[node].size(); i++)
{
int nextNode = graph[node][i];
int nextCost = cost + 1;
if (dist[nextNode] > nextCost)
{
dist[nextNode] = nextCost;
pq.push({ nextCost, nextNode });
}
}
}
int result = 1;
int cnt = 1;
for (int i = 2; i <= N; i++)
{
if (dist[result] < dist[i])
{
cnt = 1;
result = i;
}
else if (dist[result] == dist[i])
{
cnt++;
}
}
cout << result << " " << dist[result] << " " << cnt << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 2186번 문자판  (7) 2019.10.03
백준 5635번 생일  (2) 2019.10.02
백준 1516번 게임 개발  (0) 2019.09.29
백준 1766번 문제집  (0) 2019.09.29
백준 16674번 2018년을 되돌아보며  (0) 2019.09.25