[백준] 백트래킹 - 2210. 숫자판 점프

문제

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

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

 

입력

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

 

출력

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

 

예제 입력1

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

 

예제 출력1

15

 

힌트

111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.

 

생각

숫자 중복체크를 어떻게 해야 하나 고민했었다. 처음작성했던 코드는 시간초과가 났다. 오타때문에 그런 것 같기도 하고 배열에 6자리숫자 값 넣고 중복체크 true, false 하려했었다. 

검색해보니 set이라는 자료형이 있더라. 중복을 제거하지 않는 게 특징이고, 중복을 허용하려면 multiset을 사용해야한다.

정답률처럼 쉬운 문제는 아니었던 거 같은데 흠... 

 

http://www.cplusplus.com/reference/set/set/

set - C++ Reference

 

작성한 코드

#include <iostream>
#include <set>
 
using namespace std;
 
int digit[5][5];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int num;
set<int> s;
 
void DFS(int x, int y, int n){
    int temp = 0;
    if(n == 6){
        s.insert(num);
        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)
            continue;
        temp = num;
        num = (num * 10) + digit[nx][ny];
        DFS(nx, ny, n+1);
        num = temp;
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            cin >> digit[i][j];
        }
    }
    
    for(int i=0; i<5; i++){
       for(int j=0; j<5; j++){
           DFS(i, j, 0);
       }
    }
    
    cout << s.size();
    
    return 0;
}