BOJ_2210 : 숫자판 점프

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

(이하생략)

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <queue>

using namespace std;
int n,m;
int arr[5][5];
bool check[1000000];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

void bfs(int a, int b) {
	queue<tuple<int,int,int,int>> q;
	q.push(make_tuple(a,b, arr[a][b], 1));
	// 좌표, 누적값, 이동횟수

	while (!q.empty()) {
		int x, y, val, index;
		tie(x, y, val, index) = q.front();
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
			if (index == 5) {
				int valn = (val * 10) + arr[nx][ny];
				check[valn] = true;
				continue;
				// 6번째는 체크만 한다.
			}
			else {
				int valn = (val * 10) + arr[nx][ny];
				q.push(make_tuple(nx, ny, valn, index + 1));
			}

		}

	}

	

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			bfs(i, j);
		}
	}

	int ans = 0;
	for (bool ok : check)
		if (ok) ans++;
	cout << ans << '\n';

	return 0;
}