[Baekjoon] 숫자판 점프

👀 문제 설명

문제

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

 

✍🏻풀이

DFS(재귀)를 사용해 문제를 풀면 된다.

재귀함수 getAnswer는 pair<int, int> cur, int n, int sum 이라는 인자를 받는다.

pair<int, int> cur는 현재 위치를 나타내는 것이고,

int n은 숫자의 자리수를 받아온다. (나는 0부터 시작했으므로, n이 5일 때 재귀함수가 return한다.)

int sum은 현재까지 만들어진 수를 나타낸다.

 

여기서 중복된 값을 빼주기 위해 vector 대신 set 이라는 자료 구조를 사용했다.

set은 key라 불리는 원소들의 집합으로 이루어진 컨테이너로, key 값은 중복이 허용되지 않는다. 특히, 원소가 insert 함수에 의해 삽입이 되면, 원소는 자동으로 정렬이 되는 성질을 갖고 있다.

 

만약 벡터를 사용해서 중복이 되는 원소를 삭제하려면,

sort와 unique, erase를 사용한다. 이 때, sort와 unique를 사용하기 위해 algorithm 헤더를 포함해야 한다.

sort(v.begin(), v.end()); 로 벡터를 정렬하고,

v.erase(unique(v.begin(), v.end()), v.end()); 로 중복되는 원소를 삭제할 수 있다.

 

코드

#include <stdio.h>
#include <iostream>
#include <set>

using namespace std;

int digit[5][5];
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };
set<int> v;

void getAnswer(pair<int, int> cur, int n, int sum) {
    if (n == 5) {
        v.insert(sum);
        
        return;
    }
    
    for (int i = 0; i < 4; i++) {
        int nextX = cur.first + dx[i];
        int nextY = cur.second + dy[i];
        
        if (nextX < 0 || nextX >= 5 || nextY < 0 || nextY >= 5)
            continue;
        
        getAnswer({ nextX, nextY }, n + 1, sum * 10 + digit[nextX][nextY]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    
    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++) {
            getAnswer({ i, j }, 0, digit[i][j]);
        }
    }
    
    cout << v.size();
    
    return 0;
}