Baekjoon 6118 숨바꼭질

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

소스결과 3724 KB / 16 ms

언어 C++ 17

출처 Baekjoon

분류 BFS, 최단거리 알고리즘

 

설명

수혀니와 재서기가 숨바꼭질을 할 때 가장 멀리 있는 지점 중 가장 작은 번호와, 거리, 같은 지점의 개수를 출력해주자.

 

가중치도 없고, 단순히 거리만 있는 문제이기에 크게 생각할 점이 없다.

최대 지점의 수가 2만이기에 인접 행렬을 사용하지 않아야 한다.

최소 거리만 저장하면 되기에 방문체크도 간단하다.

BFS이후 거리를 저장해 가장 작은 번호 출력하고, 거리, 지점을 계산한다.

 

알고리즘

1. n, m, 간선 정보를 입력 받는다.

2. 수혀니가 1번에서 시작하기 때문에 1번을 기준으로 BFS를 시작한다.

 2-1. 현재 위치를 기준으로 인접한 노드를 방문한다.

 2-2. 방문 체크는 거리를 저장하는 배열을 이용하며 현재 노드까지의 거리 + 1을 한다.

3. 1번을 제외한 노드들 중 번호가 가장 작은 최대 거리 노드를 찾는다.

4. 3번에서 구한 최대 거리와 같은 노드의 개수를 구한다.

5. 3, 4번에서 구한 결과값을 공백으로 나누어 출력한다.

 

소스코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 20000;

vector<vector<int>> adj;

int dist[MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	queue<int> q;

	cin >> n >> m;

	adj.resize(n);

	for (int i = 0; i < m; i++)
	{
		int to, des;

		cin >> to >> des;

		adj[to-1].push_back(des-1);
		adj[des-1].push_back(to-1);
	}

	q.push(0);

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		int curNodeCount = adj[cur].size();

		for (int i = 0; i < curNodeCount; i++) {
			int next = adj[cur][i];

			if (dist[next] == 0) {
				dist[next] = dist[cur] + 1;
				q.push(next);
			}
		}
	}

	int maxDist = 1;
	for (int i = 2; i < n; i++)
		if (dist[maxDist] < dist[i])
			maxDist = i;

	int sameCount = 0;
	for (int i = 1; i < n; i++)
		if (dist[maxDist] == dist[i])
			sameCount++;

	cout << maxDist + 1 << ' ' << dist[maxDist] << ' ' << sameCount;

	return 0;
}