문제 링크입니다: 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로 설정하였습니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |


개발환경: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 |