[백준/c++] BOJ 2210 - 숫자판 점프

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

2210번: 숫자판 점프

 

문제 설명

5x5 크기의 숫자판이 있다. 각 칸에는 0부터 9까지의 숫자가 적혀 있다. 임의의 위치에서 시작해서, 인접한 다섯 방향으로 이동하면서, 각 칸에 적혀 있는 숫자를 차례로 붙이면 6자리 수가 만들어진다. 한 번 거쳤던 칸을 다시 거쳐도 되며, 만들 수 있는 서로 다른 여섯 자리 수들의 개수를 구한다.

해결

모든 칸에서의 시작을 고려해야 하므로 브루트포스로 접근하였다.

각각의 칸에서 시작하여, dfs를 돌려 준다.

나올 수 있는 숫자는 최대 999999이므로, vistied 배열의 크기는 1000000로 잡아 주었다.

 

한 번 거쳤던 칸을 다시 거쳐도 되므로, 방문한 칸을 고려하지 않아도 된다.

다섯 번 이동 후에 dfs가 끝나게 하고, 만들어진 숫자가 이미 만들었던 숫자라면 그대로 리턴한다.

처음 나온 숫자라면 ans를 증가시켜 카운트 해 준다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int board[5][5];
int visited[1000000];
int ans = 0;
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };

int range_over(int i, int j) {
    return i < 0 || j < 0 || i >= 5 || j >= 5;
}

void dfs(int i, int j, int result, int cnt) {
    if (cnt == 5) {
        if (visited[result]) return;
        visited[result] = 1;
        ans++; return;
    }

    for (int dir = 0; dir < 4; dir++) {
        int nx = i + dx[dir], ny = j + dy[dir];
        if (range_over(nx, ny)) continue;

        int results = result * 10 + board[nx][ny];
        dfs(nx, ny, results, cnt + 1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++)
            cin >> board[i][j];
    }

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            dfs(i, j, board[i][j], 0);
        }
    }

    cout << ans;
}