[백준] 2210 - 숫자판 점프

백준 온라인 저지에 수록되어있는 문제의 설명과 풀이 및 소스 코드를 작성한 글입니다.

---

💡 문제

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

💡 풀이

시간복잡도를 먼저 구해보자. 숫자판의 크기가 정해져 있으므로 임의의 시작점을 정하고, 인접한 지점으로 5번 이동할 때 가능한 총 경우의 수는 다음과 같다.

이는 25600이므로 그렇게 큰 수가 아니다. 따라서 모든 경우의 수를 따져보는 브루트 포스 문제라고 할 수 있다.

이 문제는 총 3단계로 풀 수 있다.

1. 시작 위치 선택(5^2가지)

2. 인접한 위치로 5번 이동하여 여섯 자리 수 구하기(4^5가지)

3. 중복된 수 제거하기

3번째 단계를 구현하는 방법은 여러 가지가 있겠지만 C++ vector에 저장하고 중복된 값을 제거하는 방법(소스 코드 1)을 선택하거나, 또는 C++ set이라는 컨테이너를 사용하는 방법(소스 코드 2)을 선택해도 된다. set 컨테이너는 C++ vector와 달리 중복을 허용하지 않고 저장하여 훨씬 구현이 쉬워진다.

💡 소스 코드

소스 코드 1 - vector 컨테이너

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
# define N 5

int map[N][N];

vector<int> v;  

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

// 재귀함수
void recursive(int x, int y, int num, int len) {
	
	if (len == 6) { // 숫자가 여섯자리가 된 경우
		v.push_back(num);
		return;
	}

	for (int k = 0; k < 4; k++) { // 인접한 곳으로 이동
		int nx = x + dx[k];
		int ny = y + dy[k];

		if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
			recursive(nx, ny, num * 10 + map[nx][ny], len + 1); 
		}
	}
}

int main() {
	// 입력
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			recursive(i, j, map[i][j], 1); // 시작점 : map[i][j], 시작할 때 길이 : 1
		}
	}

	// 벡터 중복 값 제거
	sort(v.begin(), v.end()); // 정렬
	v.erase(unique(v.begin(), v.end()), v.end()); // 제거

	cout << v.size() << '\n';

	return 0;
}

소스 코드 2 - set 컨테이너

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
# define N 5

int map[N][N];

set<int> s; // 중복을 허용하지 않는 set 컨테이너

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

// 재귀함수
void recursive(int x, int y, int num, int len) {
	
	if (len == 6) { // 숫자가 여섯자리가 된 경우
		s.insert(num);
		return;
	}

	for (int k = 0; k < 4; k++) { // 인접한 곳으로 이동
		int nx = x + dx[k];
		int ny = y + dy[k];

		if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
			recursive(nx, ny, num * 10 + map[nx][ny], len + 1); 
		}
	}
}

int main() {
	// 입력
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			recursive(i, j, map[i][j], 1); // 시작점 : map[i][j], 시작할 때 길이 : 1
		}
	}

	cout << s.size() << '\n';

	return 0;
}

💡 풀이 후기

그렇게 어려운 난이도는 아닌 문제였다.

이 숫자판 점프 문제의 핵심은 어떻게 중복을 제거할지였다. C++ set 컨테이너를 사용한다면 엄청 쉬워지겠지만 아마 코딩 테스트였다면 절대 생각나지 않았을 것이다. 하지만 vector의 중복 값을 제거하는 방법도 나쁘지 않은 것 같다.