[백준OJ] 6118번 숨바꼭질

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

6118번: 숨바꼭질

---

 

-풀이-

간단한 BFS문제이다. BFS를 이용하여 각 방까지의 최단거리를 모두 구해준 뒤, 최단거리가 가장 큰 방( 같은 값이 두개이상 있다면, 방번호가 작은방) 을 구해준 뒤, 해당 방과 거리가 같은 방들의 개수를 구해준다음 모두 출력해주면된다.

 

-시간복잡도-

BFS알고리즘은 O(V+E)이므로, 여기선 O(N+M)이 된다.

나머지 구해주는 로직은 모두 O(N)선에서 끝나므로, 최종 시간복잡도는 O(N+M)이 된다.

 

-코드-

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

vector<int> maze[20001];
int visited[20001] = { 0 };
int n, m;

void make_graph() {
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		maze[a].push_back(b);
		maze[b].push_back(a);
	}
}
void input() {
	cin >> n >> m;
	make_graph();
}


void bfs() {
	queue<pair<int, int>> q;
	q.push({ 1,1 });
	visited[1] = 1;

	while (!q.empty()) {
		int now = q.front().first;
		int dist = q.front().second;
		q.pop();

		for (int next : maze[now]) {
			if (!visited[next]) {
				visited[next] = dist + 1;
				q.push({ next,dist + 1 });
			}
		}
	}

	int max = 0;
	int max_cnt = 0;
	int maxNode = -1;

	for (int i = 2; i <= n; i++) {
		if (max < visited[i]) {
			max = visited[i];
			maxNode = i;
		}
	}
	for (int i = 2; i <= n; i++) {
		if (max == visited[i]) max_cnt++;
	}
	cout << maxNode << " " << visited[maxNode] - 1 << " " << max_cnt;
}


void solve() {
	input();
	bfs();
}

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

	return 0;
}