C++ 백준 6118 숨바꼭질

백준 6118

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

6118번: 숨바꼭질

풀이 전 나의 생각

재서기는 수혀니로부터 발냄새가 최대한 나지 않기 위해 멀리 떨어져야 한다.

 

헛간의 정보가 주어질 때, 수혀니가 있는 1번 헛간으로부터 헛간의 위치, 최대한 멀리 떨어진 거리,

동일 거리의 헛간 개수를 구해야 한다.

 

조건

- 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다.

- M(1<= M <= 50,000)개의 양방향 길

- 어떤 헛간에서 다른 헛간으로는 언제나 도달 가능

 

과정

헛간의 정보가 양방향 그래프의 형태로 주어진다.여기서 주의할 점은 수혀니는 1번 헛간에 있고, 헛간은 양방향 길이라는 것이다.

	             1--2--5
                   | /|
                   |/ |
                   3--4
                   |
                   6

 

그리고 헛간의 정보를 DFS로 탐색하게 된다면 (1 - 2 - 4 - 6), (1 - 2 - 3 - 6).. 이런 형식으로 깊이 우선 탐색을 진행하기 때문에 현재 노드와 연결된 노드부터 탐색하는 BFS(너비 우선 탐색)를 사용하는 것이 좋다.

 

문제에서 요구하는 결과는 숨어야 하는 헛간의 위치, 헛간의 거리, 헛간의 개수를 구해야 하기 때문에BFS로 헛간을 탐색할 때 마다 거리 정보를 저장하는 과정을 거쳐야 한다. 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>>link(20001);
bool visited[20001];
int hide_dist[20001];

void bfs(int st)
{
	visited[st] = true;
	queue<pair<int, int>> q;
	q.push(make_pair(st, 0));

	while (!q.empty())
	{
		int now_node = q.front().first;
		int now_dist = q.front().second;
		q.pop();

		//탐색 진행과 동시에 거리 정보 저장
		hide_dist[now_node] = now_dist;

		for (int next : link[now_node])
		{
			if (!visited[next])
			{
				visited[next] = true;
				q.push(make_pair(next, now_dist + 1));
			}
		}
	}
}

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

	int N, M, hide = -1, ans = 0, cnt = 0;
	cin >> N >> M;
	
	//헛간의 정보 저장(양방향)
	for (int i = 0; i < M; i++)
	{
		int A_i, B_i;
		cin >> A_i >> B_i;

		link[A_i].push_back(B_i);
		link[B_i].push_back(A_i);
	}

	//수혀니는 헛간 1번에 위치
	bfs(1);
	
	//구해 놓은 헛간 거리의 최대값
	for (int i = 1; i < N; i++)
	{
		if (ans < hide_dist[i])
		{
			ans = hide_dist[i];
		}
	}
	//숨어야 하는 헛간, 최대 거리와 같은 헛간 개수
	for (int i = 1; i <= N; i++)
	{
		if (ans == hide_dist[i])
		{
			if (hide == -1) hide = i;

			cnt++;
		}
	}
	cout << hide << " " << ans << " " << cnt;
}