[BaekJoon/백준] 2210번 숫자판 점프

O(n^3) 은 나오려나..

n <= 5 니까 무난하게 할 수 있다.

 

각 위치에서 dfs 사용하여 구현한다.

#include <iostream>
#include <set>
#include <string>

using namespace std;

// 상 하 좌 우
int sx[4] = {-1, 1, 0, 0};
int sy[4] = {0, 0, -1, 1};

int MATRIX[5][5];

set<string> s;

char temp[6];

void dfs(int x, int y, int count) {
    
    int mx, my;
    
    
    temp[count] = MATRIX[x][y] + 48;
    
    
    
    if(count == 5) {
        s.insert(temp);
        return;
    }
    
    for(int i = 0; i < 4; i++) {
        
        mx = x + sx[i];
        my = y + sy[i];
        
        if(mx < 0 || mx > 4 || my < 0 || my > 4)
            continue;
        
        dfs(mx, my, count + 1);
        
    }
}

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            
            cin >> MATRIX[i][j];
        }
    }
    
    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            
            dfs(i, j, 0);
        }
    }

    
    cout << s.size() << "\n";
    
    
}

/*
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
*/