백준 6118 숨바꼭질

작성일 | In |

Problem : 숨바꼭질

유형 : 그래프, BFS

문제 해석

  • 1번 헛간으로부터 가장 멀리 떨어진 헛간과, 그 중에서 가장 작은 번호의 헛간, 헛간의 개수를 구하라.

문제 재해석

  • 연결 그래프라는 조건이 있다.
  • 1번 헛간으로부터의 거리를 재는 것이다.

해결 전략

  • 1번 헛간으로부터의 거리를 구하는 것이므로, BFS로 풀어야 한다.

설계, 구현

  • 인접 리스트를 이용하여 그래프 노드간의 관계를 설정한다.
  • 1번 노드부터 BFS를 이용해 그래프를 순회한다.
  • 각 거리에 따른 헛간 번호들을 저장해둔다.
  • 가장 먼 헛간을 구했으면, 정렬후 답을 구한다.

주의할 점

  • 거리를 잴 때, 마지막 단계 (아무 곳도 못 가는 단계) 에서 dist가 1 증가한다.
  • 마지막에 dist를 -1 해어야 진짜 max_dist를 구할 수 있다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

vector<int> node[20002], dist_vec[20002];
queue<int> q;

bool visit[20002];
int n, m;

int Bfs() {
	int dist = 0;
	while (!q.empty()) {
		dist++;
		int q_size = (int)q.size();
		while (q_size--) {
			int cur_barn = q.front();   q.pop();

			for (const auto& nxt_barn : node[cur_barn]) {
				if (visit[nxt_barn]) continue;
				visit[nxt_barn] = true;
				dist_vec[dist].push_back(nxt_barn);
				q.push(nxt_barn);
			}
		}
	}
	return dist - 1;
}

void Solve() {
	dist_vec[0].push_back(1);
	visit[1] = true;
	q.push(1);

	int max_dist = Bfs();
	sort(dist_vec[max_dist].begin(), dist_vec[max_dist].end());
	cout << dist_vec[max_dist][0] << " " << max_dist << " " << (int)dist_vec[max_dist].size() << "\n";
}


void Input() {
	cin >> n >> m;

	int a, b;
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		node[a].push_back(b);
		node[b].push_back(a);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);  cout.tie(NULL);
	freopen("input.txt", "r", stdin);

	Input();
	Solve();

	return 0;
}

피드백

  • 이런 쉬운 문제도 푸는데 30분이 걸렸다.
  • 집중해서 빠르게 문제를 풀도록 하자.