[백준알고리즘] 2210번: 숫자판 점프 -C++

[백준알고리즘] 2210번: 숫자판 점프 -C++

2210번: 숫자판 점프 (acmicpc.net)

2210번: 숫자판 점프

메모이제이션을 사용할까 하다가 숫자판도 작고, 만들어낼 숫자의 길이도 6자리로 길지 않았기 때문에 계산을 해보다가 메모이제이션 없이 완전 탐색을 시도했다.

 

대강 계산했을 때 각 위치에서 4방향으로 이동할 수 있기 때문에 메모이제이션 없이 각 시작 위치에서 \(4^5\)개의 위치로 이동할 수 있다. 즉, \(5 \times 5 \times 4^5\)개를 이동할 수 있다. 이 값은 \( 25,600 \)으로 연산양이 충분히 적은 것을 알 수 있다. 따라서 충분히 연산이 빠르게 되기 때문에 메모이제이션 없이 계산했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제는 DFS를 이용해서 해결했다. 각 시작 위치를 루트로 해서 DFS로 이동 가능한 경로를 모두 탐색했다. 그리고 길이가 6이 되는 숫자열을 만든다면, 해당 숫자열을 set에 집어넣었다. 그렇게 각 시작 위치를 모두 돌아가면서 해주기 위해 \(5 \times 5\) 번의 호출을 해주었고, 최종적으로 set에 있는 원소의 개수를 출력해주면서 가능한 정수열을 출력해주었다.

 

문제에서 0으로 시작하는 수도 확인해줘야 한다고 하는데, 이는 문자열로 처리하면 동일하게 처리할 수 있다. 숫자로 하더라도 '123'이 '000123'을 의미하는 것으로 계산을 해주면 결국 동일하게 해결할 수 있기 때문에 쉽게 풀 수 있었다.

 

아래는 C++로 푼 문제의 풀이이다. memset을 사용하기 위해 <cstring>을 포함시켰다.

#include <iostream>
#include <set>
#include <cstring>

std::set<int> answer;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void solve(void);

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

void dfs(int (&board)[6][6], int i, int j, int length, int number = 0)
{
	if (length == 0)
	{
		answer.insert(number);
		return;
	}

	for (int d = 0; d < 4; d++)
	{
		int x = j + dx[d];
		int y = i + dy[d];

		if (x <= 0 || 5 < x || y <= 0 || 5 < y)
			continue;

		dfs(board, y, x, length - 1, number * 10 + board[y][x]);
	}
}

void solve(void)
{
	int board[6][6];
	memset(board, 0, sizeof(board));
	for (int i = 1; i <= 5; i++)
		for (int j = 1; j <= 5; j++)
			std::cin >> board[i][j];

	for (int i = 1; i <= 5; i++)
		for (int j = 1; j <= 5; j++)
			dfs(board, i, j, 6);

	std::cout << answer.size();
}