[BOJ] 2210. 숫자판 점프

https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

이동하는 칸에 있는 숫자를 합쳐서 서로 다른 6자리의 수를 만드는 문제이다.

set을 사용하면 중복을 제거하여 서로 다른 수를 쉽게 만들 수 있다.

 

먼저 모든 칸에서 네 방향으로 움직여본다.

중복이 가능해서 오래 걸릴 것 같지만 시간 복잡도를 대충 계산해보면

5*5 (모든 칸에서 시작) * 4^5 (네가지 방향으로 다섯 번 이동) 이므로 생각보다 적다.

 

이동할 때마다 현재 숫자에 곱하기 10을 해줘서 자릿수를 앞으로 당겨주고 현재 칸의 값을 더해준다.

예를 들어 123이었고 현재 칸이 4라면 123*10 + 4를 해줘서 1234를 만들 수 있다.

 

5번 이동을 마치고 6자리 숫자가 되었다면 set에 추가해준다.

모든 칸에 대해서 이동을 마쳤다면 set의 사이즈(서로 다른 6자리수의 개수)를 출력해주면 된다.

 

#include <iostream>
#include <set>
using namespace std;
 
int map[5][5];
set<int> s;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void solve(int x, int y, int cnt, int num) {
    //다섯번 이동했으면 합친 숫자를 set에 넣어준다.
    if (cnt >= 5) {
        s.insert(num);
        return;
    }
 
 
    //네 방향으로 이동
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
 
        //범위 체크
        if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
 
        //기존의 숫자에 10을 곱해준뒤 현재 칸의 숫자를 더해준다.
        solve(nx, ny, cnt + 1, num*10+map[nx][ny]);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> map[i][j];
        }
    }
 
    //모든 점에서 출발해본다.
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            solve(i, j, 0, map[i][j]);
        }
    }
 
 
    //set의 크기를 출력
    cout << s.size();
 
    return 0;
}