BOJ 2210 Hopscotch(숫자판 점프) C++

문제

상,하,좌,우 4방향으로 움직일 수 있다.

만들 수 있는 모든 숫자 경우의 수를 찾으면 된다.

접근 방법

🌟 5*5로 작은 배열이므로 DFS를 이용한 완전 탐색이 가능하다

🌟 각 칸의 숫자는 digit이기 때문에 최대 숫자로 999999 정도다

🌟 set를 이용해 중복을 제거한다.

 

코드

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int N = 5;
vector<vector<int>> m;
set<int> s;
int dx[4] = { 0, 1, 0, -1};
int dy[4] = { 1, 0, -1, 0};

void dfs(int depth, int x, int y, int num)
{
    if(depth == 5) {
        s.insert(num);
        return;
    }
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N)  {   continue;   }
        dfs(depth+1, nx, ny, 10*num + m[nx][ny]);
    }
}

int main()
{
    for(int i = 0; i < N; i++) {
        vector<int> v(N);
        for(int j = 0; j < N; j++) {
            cin >> v[j];
        }
        m.push_back(v);
    }
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            dfs(0, i, j, m[i][j]);
        }
    }
    cout << s.size();
    
    return 0;
}