백준 2210번 숫자 판 점프 풀이(c++)

문제

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

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

입력

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

출력

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

 

처음에는 5중for문을 돌려서 찾다가 이건 아닌거같아서 다른 블로그에서 dfs 를 이용하는걸 보고 참고해서 풀었다.

dfs 는해당 깊이탐색인데 내가 count 를 둬서 5개까지만 탐색을 했고 set 자료구조를 써서 insert 할때 중복값은 제거 한후 해당 set의 사이즈를 출력해 주었다.

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int arr[5][5];
set<int>setSum;


int xx[4] = { 1, -1, 0, 0 };
int yy[4] = { 0, 0, 1, -1 };

void dfs(int x, int y, int count, int num)
{
	if (count == 5)
	{
		setSum.insert(num);
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int px = x + xx[i];
		int py = y + yy[i];

		if (px < 0 || py < 0 || px >= 5 || py >= 5)
			continue;
		dfs(px, py, count + 1, num * 10 + arr[px][py]);
	}
}

int main()
{
	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++) //y
	{
		for (int j = 0; j < 5; j++) //x
			dfs(j, i, 0, arr[j][i]);
	}

	cout << setSum.size() << '\n';
}