백준 2210번 숫자판 점프 - C++ 풀이

---

 

1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다.

 

1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다.

 5번 이동하므로 총 탐색해야 하는 상태 수는 25 * (4^5)로 매우 적기 때문에 브루트 포스로 해결할 수 있다. DFS를 통해 모든 경우를 구해서, 만들 수 있는 모든 수를 구해준다.

 

반응형

---

#include <iostream>
#include <unordered_set>

using namespace std;

int board[5][5];
unordered_set<int> st;

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void DFS(int n, int r, int c, int curr) {
    if (n == 6) {
        st.insert(curr);
        return;
    }
    
    for (int i=0; i<4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
        
        DFS(n+1, nr, nc, curr*10 + board[nr][nc]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            cin >> board[i][j];
        }
    }
    
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            DFS(1, i, j, board[i][j]);
        }
    }
    
    cout << st.size();

    return 0;
}