백준 6118번 - 숨바꼭질

문제링크

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

6118번: 숨바꼭질

시작지점인 1번에서 가장 멀리있는 지점의 거리와 같은 거리를 갖는 지점중 가장 낮은 번호를 갖는 지점 그리고 같은 거리를 갖는 지점의 개수를 출력하는 문제입니다.

문제에서 길은 양방향으로 취급하기 때문에 인접행렬 형식으로 길 정보를 저장하였습니다.

다익스트라 알고리즘을 활용하였고 모든 길은 가중치가 동일하기 때문에 가중치를 따로 저장하지 않았습니다.

 

다익스트라 알고리즘으로 1번 시작위치에서 모든 지점까지 가는 길이를 각각 구하고 마지막에 정렬을 통해 가장 먼 거리를 구합니다.

 

마지막에 순차탐색으로 각 지점까지의 거리와 가장먼거리를 비교해서 가장 먼저 같은 위치의 번호, 같은 위치의 개수를 구하고 정답을 출력하였습니다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <queue>
 
using namespace std;
 
#define MAX_M 50001
#define MAX_N 20001
#define INF 987654321
 
//typedef struct NODE {
//	int weight;
//	int end;
//};
 
vector<int> edge[MAX_M];
 
int dist[MAX_N];
int start_node, N, M;
 
//int index[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };//아래 오른쪽 위 왼쪽 순서대로
 
void dijkstra() {
	priority_queue<pair<int , int>> pq;
	pq.push({ 0, start_node });
	int now_node;
 
	while (pq.empty() == false) {
		now_node = pq.top().second;
		pq.pop();
		for (int i = 0; i < edge[now_node].size(); i++) {
			int new_value = dist[now_node] + 1;
			int before_value = dist[edge[now_node][i]];
 
			if (new_value < before_value) {
				dist[edge[now_node][i]] = new_value;
				pq.push({-1*new_value, edge[now_node][i] });
			}
		}
	}
}
 
bool compare(pair<int , int> a, pair<int,int> b) {
	return a.second < b.second;
}
 
void debug() {
 
}
void clear() {
}
 
int main()
{
	int max_value;
	scanf("%d %d", &N, &M);
	start_node = 1;
	int start, end, weight;
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &start, &end);
		edge[start].push_back(end);
		edge[end].push_back(start);
	}
	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}
 
	dist[1] = 0;
 
	dijkstra();
 
	max_value = *max_element(dist + 1, dist + N);
	int count = 0;
	int idx;
	for (int i = 1; i <= N; i++) {
		if (dist[i] == max_value) {
			count++;
			if (count == 1)
				idx = i;
		}
	}
 
	printf("%d %d %d", idx, max_value, count);
}