백준 2210 - 숫자판 점프

백준 2210 문제 바로가기

풀이

5x5 숫자판이 주어질 때 임의의 위치에서부터 [상, 하, 좌, 우] 방향으로 다섯 번 이동하여 만들 수 있는 서로 다른 6자리의 숫자의 개수를 구하는 문제이다.

임의의 위치에서 시작하여 상하좌우 방향으로 DFS를 수행하면서 함수의 매개변수(int len)가 6이 될 때까지 반복한다.

숫자를 우측에 이어붙여 나가는 식은 다음과 같은데 num * 10 + field[nr][nc]

이때 만들어지는 숫자를 chk 배열의 인덱스로 이용하여 true로 표시하여 중복 여부를 판별하였다.

그리고 임의의 위치라고 했으므로 이중 for문을 활용하여 25개의 모든 (r, c)칸에서 solve함수를 호출하여 정답을 구할 수 있다.

아래는 풀이를 위한 핵심 코드이다.

const int dr[] = { -1,1,0,0 };
const int dc[] = { 0,0,-1,1 };
int field[5][5];
int ans;
bool chk[1000000];

void solve(int r, int c, int len, int num) {
    if (len == 6) {
        if (!chk[num]) {
            chk[num] = true;
            ++ans;
        }
        return;
    }
    
    for (int d = 0; d < 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
        solve(nr, nc, len + 1, num * 10 + field[nr][nc]);
    }
}