백준/6118/BFS/숨바꼭질

백준/6118/BFS/숨바꼭질

문제 해석

숨바꼭질을 하는데 술래가 시작하는 위치인 1로 부터 가장 먼 헛간을 구하는 문제입니다.

문제 풀이

1에서 부터 BFS를 시작하여 거리를 저장하고 이 중에서 거리가 가장 큰 값을 구하고 해당 값과 같은 인덱스의 수와 가장 먼저 발견된 인덱스를 출력합니다.

풀이

첫번째 풀이

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int> map[20'001];
int visited[20'001];

queue<int>q;

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

	// N은 헛간의 개수, M은 길의 개수
	int N, M = 0;

	cin >> N >> M;

	for (int i = 0;i < M;i++)
	{
		int _a, _b = 0;
		cin >> _a >> _b;
		map[_a].push_back(_b);
		map[_b].push_back(_a);
	}

	q.push(1);
	visited[1] = 0;

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

		for (int _idx = 0;_idx < map[cur].size();_idx++)
		{
			int nxt = map[cur][_idx];
			if (!visited[nxt] && nxt != 1)
			{
				visited[nxt] = visited[cur] + 1;
				q.push(nxt);
			}
		}
	}

	int _max = 0;

	int result = 0;
	int _count = 0;

	for (int i = 1;i <= N;i++)
	{
		if (_max < visited[i])
		{
			_max = visited[i];
			result = i;
		}
	}


	for (int i = 0;i <= N;i++)
	{
		if (_max == visited[i])
			_count++;
	}

	cout << result <<' ' << _max <<' ' << _count;

	return 0;
}