[백준/C++] 22120 숫자판 점프

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

코드

#include <iostream>
using namespace std;

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
int arr[5][5], ans = 0;
bool visit[1000000];

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

void dfs(int x, int y, int sum, int cnt) {
	if (cnt == 5) {
		if (!visit[sum]) {
			visit[sum] = true;
			ans++;
		}
		return;
	}

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

		if (gx >= 0 && gy >= 0 && gy < 5 && gx < 5)
			dfs(gx, gy, sum * 10 + arr[gx][gy], cnt + 1);
	}
}

int main() {
	FASTIO;
	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++)
			dfs(i, j, arr[i][j], 0);

	cout << ans;
	return 0;
}

 

설명

현재 위치에서 dfs로 5번 이동하며 만들 수 있는 숫자의 개수를 구합니다. dfs 시에는 한 번 거쳤던 칸을 지나도 되므로 이동 과정에서는 방문 처리를 할 필요가 없습니다. 최종적으로 얻게 되는 값이 현재까지 나온 적이 없으면 visit 배열에 true로 표시 후 결과 개수를 증가시킵니다. 이후 결과 개수를 출력합니다.

 

느낀 점

기본적인 dfs 문제입니다.