[백준 2210번] 숫자판 점프

문제 설명

5×5 크기의 숫자판이 있다.
각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다.

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

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

입력

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

출력

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

알고리즘

깊이 우선 탐색(DFS, Depth-First Search)

접근 방식 및 풀이

5×5 크기의 숫자판 안에서 서로 다른 여섯 자리의 수들을 탐색하는 것은 결국 숫자’길‘을 탐색하는 것과 같다. 그렇기 때문에 완전 탐색 알고리즘 중 하나인 깊이 우선 탐색(DFS, Depth-First Search)를 사용했다.

탐색을 위한 DFS 함수는 인접한 지점(해당 문제에 경우 상하좌우)으로 이동 시 해당 지점에 대해서 다시 DFS 함수를 실행하는 재귀 함수 형태로 구현했다.

여기서 고려해야할 점이 몇가지 있다.

한번 거쳤던 칸을 다시 거쳐도 된다는 조건이 있기 때문에 방문한 지점을 따로 체크하지 않는다.

사실 이 점은 오히려 일반적인 DFS에서 고려해야할 사항이 없어진 것이기에 넘어가겠다.

5x5 숫자판 내에서 움직여야한다.

DFS 함수가 호출되었을 때 현재 row와 col의 위치를 확인해 숫자판의 범위를 넘어갔을 경우 함수를 종료시켰다.

계속 이동하는 것이 아니라 다섯 번 이동 후 멈춰야한다.

이동 횟수를 카운드하는 int 변수를 사용했다. DFS 함수를 시작하기 전에 이동 횟수를 0으로 설정하고 함수를 다시 부를 때마다 이동 횟수를 하나씩 늘렸다. 그리고 DFS 함수 내에 if문을 통해 이동 횟수가 5인지를 확인하여 5일 경우 해당 지점에서 더 이상 DFS를 들어가지 않았다.

여러번 등장하는 숫자길이 존재할 수 있기 때문에 이미 등장한 숫자길인지 확인해야한다.

체크를 위한 bool 배열를 선언했다. 0~9의 숫자가 6번 반복되면 0~999999(10의 6승) 범위의 숫자가 나올 수 있기 때문에 배열의 크기는 1000000으로 설정했다.

다섯 번의 이동을 통해 도출한 여섯 자리의 숫자에 해당하는 bool 값을 확인했을 때
이미 true라면 이전에 이미 등장했던 것이기 때문에 넘어가고
false라면 처음 나온 것이기 때문에 true로 바꿔서 다음에 재등장 시 알 수 있게 했다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>
#include <stdbool.h>

void move(int row, int col, int moving, int tem_way[6]);
void check_save();

int input[5][5]; // 5x5 숫자판을 받기 위한 이차 array
bool check[1000000]; // 이미 나왔던 숫자인지 확인하기 위한 bool array
int n_ways = 0; // 숫자 조합의 개수

int
main(){
    int tem_way[6]; // 현재 움직이고 있는 길을 저장하기 위한 int array
    int moving = 0; // 움직인 횟수(5번 움직이면 끝)
    
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            scanf("%d\n", &input[i][j]);
        }
    }
    
    // 시작점을 옮겨가면서 dfs 함수를 실행한다. (0,0부터 4,4까지)
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            move(i, j, moving, tem_way);
        }
    }
    
    printf("%d\n", n_ways);
    return 0;
}

// 움직임을 관리하는 dfs 함수
void move(int row, int col, int moving, int tem_way[6]){
    // 5x5 숫자판을 넘어섰을 경우
    if(row < 0 || row >= 5 || col < 0 || col >= 5){
        return;
    }
    //5번 움직였을 경우
    else if(moving == 5){
        // 현재 위치의 숫자를 저장하여 6개의 숫자길을 완성하고
        tem_way[5] = input[row][col];
        // 처음 나온 숫자길인지 확인한다.
        check_save(tem_way);
    }
    else{
        tem_way[moving] = input[row][col];
        //위쪽
        move(row - 1, col, moving + 1, tem_way);
        //오른쪽
        move(row, col + 1, moving + 1, tem_way);
        //아래쪽
        move(row + 1, col, moving + 1, tem_way);
        //왼쪽
        move(row, col - 1, moving + 1, tem_way);
    }
    return;
}

// 숫자길이 처음 나온 숫자길인지 확인하는 함수
void check_save(int tem_way[6]){
    int num;
    // 6개의 숫자를 하나의 숫자로 만든다. ex) 1,2,3,4,5,6 -> 123456(십이만삼천사백오십육)
    num = tem_way[5] * 1 + tem_way[4] * 10 + tem_way[3] * 100 + tem_way[2] * 1000 + tem_way[1] * 10000 + tem_way[0] * 100000;
    // check array 해당 숫자에 해당하는 값이 false인 경우 처음 등장하는 숫자길이므로
    if(check[num] == false){
        // 체크
        check[num] = true;
        // 숫자길 개수를 하나 늘려준다.
        n_ways += 1;
    }
    return;
}