[알고리즘] 백준 6118번: 숨바꼭질 (C++)

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

6118번: 숨바꼭질

틀렸던 문제들을 보다가 다시 보게 된 문제 중 하나였다.

다시 봐도 예전에 틀렸던(메모리 초과) 것처럼 2차원 배열을 써야 풀릴 듯했다.

하지만, 비슷한 이유에서 예전에 메모리 초과가 났던 기억이 있어서 기억을 되짚어 보았다.

---

우선 예전 코드를 보면서 왜 메모리 초과가 날 거 같았는지 되짚어 보았다.

1) 큰 크기의 2차원 배열 선언

bool map[20001][20001] = { 0, };

물론 엄청 크다고 생각하지는 않되 그렇다고 해서 무시할 수 없는 크기의 배열이어서 메모리 초과 원인 후보로 올랐다.

 

2) BFS에 for문을 수행하는 연산의 수가 너무 많다.

void bfs(int value) {
	queue<int> q;
	q.push(value);
	check[value] = 0;
	while (!q.empty()) {
		int front = q.front();

		q.pop();
		for (int i = 1; i <= n; i++) {
			if (map[front][i] && check[i] == -1) {
				check[i] = check[front] + 1;
				maxValue = max(maxValue, check[i]);
				q.push(i);
			}
		}
	}
}

예전에 썼던 BFS 코드인데 안에 for문을 보면 1~n까지 쭉 돌려보면서 갈 수 있는 헛간을 탐색하고 있다.

각각 한 노드에서 1~n까지 연산을 계속하는 건 충분히 메모리 초과를 일으킬 수 있다고 생각했다.

---

솔루션

하지만, 2차원 배열을 써야 풀릴 거 같았다. 저 2가지 단점들을 해결할 수 있는 방법을 모색하다가 예전에 풀었던 문제에서 똑같은 경우가 기억나서 2차원 동적 배열로 풀 수 있었다.

 

(영감을 받았던 문제)

https://draw-code-boy.tistory.com/98

[알고리즘] 백준 11725번: 트리의 부모 찾기 (C++), 2차원 동적 배열 (vector)

1번째 이유를 커버칠 수 있다고는 얘기를 못 하겠다. 하지만, 2차원 배열을 선언하여 푼 것보다는 더 적게 메모리를 잡아먹는다. 2차원 동적 배열을 써야겠다고 제일 크게 생각이 들었던 건 2번째 이유였다.

 

2차원 동적 배열을 사용함으로써

어떠한 헛간으로부터 갈 수 있는 헛간만 탐색을 하기 때문에 확실히 탐색의 횟수를 줄일 수 있었다.

 

[AC 코드]

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <climits>
#include <cstring>
#define MAX 20000 + 1
using namespace std;

int n, m;
vector<int> map[MAX];
//bool map[20001][20001] = { 0, };
int check[20001] = { 0, };
int maxValue = 0;

void bfs(int value) {
	queue<int> q;
	q.push(value);
	check[value] = 0;
	while (!q.empty()) {
		int front = q.front();
		//cout << front << ' ';
		q.pop();
		for (int i = 0; i < map[front].size(); i++) {
			int next = map[front][i];
			if (check[next] == -1) {
				check[next] = check[front] + 1;
				maxValue = max(maxValue, check[next]);
				q.push(next);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	memset(check, -1, sizeof(check));
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}

	bfs(1);

	int cnt = 0;
	int minValue = INT_MAX;
	for (int i = 1; i <= n; i++) {
		if (check[i] == maxValue) {
			cnt++;
			minValue = min(minValue, i);
		}
	}

	cout << minValue << ' ' << maxValue << ' ' << cnt;
	return 0;
}