[ 백준 2210 ] 숫자판 점프 (C++)

백준의 숫자판점프(2210) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 0~9 사이의 숫자가 적혀있는 5x5 숫자판에서, 임의의 위치에서 시작해서 인접해 있는 네 방향으로 총 다섯번 이동하면서

  6자리의 숫자를 만들었을 때, 만들 수 있는 숫자의 전체 갯수를 구하면 되는 문제이다.

[ 문제풀이 ]

1. 모든 정점에서 구할 수 있는 모든 숫자를 다 구해보면 되는 완전탐색 문제이다.

2. 본인은 DFS를 이용해서 구현하였는데, Depth = 5가 되면 계산을 하도록 만들어 주었다.

3. 어려운 부분은 없었고, DFS를 호출할 때 (x, y, Sum, Depth)를 이용하였고, Sum에는 계속해서 값을 더해주었다.

   물론 더할때, 그냥 더하면 안되고 x10을 해서 더해주었다.

   (예를 들어서 1다음에 2를 밟았다고 생각하면 이 때 나오는 숫자는 12 = 1x10 + 2)

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int MAP[5][5], Answer = 0;
bool Visit[1000000];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void DFS(int x, int y, int Sum, int Cnt)
{
    if (Cnt == 5)
    {
        if (Visit[Sum] == false)
        {
            Visit[Sum] = true;
            Answer++;
        }
        return;
 
    }
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5)
        {
            DFS(nx, ny, Sum * 10 + MAP[nx][ny], Cnt + 1);
        }
    }
}
void Solution()
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            DFS(i, j, MAP[i][j], 0);
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}