(C++) - 백준(BOJ) 2210번 : 숫자판 점프 답

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

2210번: 숫자판 점프

DFS문제였습니다

문제풀이 :

5 X 5 숫자판에서 각 판을 시작점으로하여 동서남북 4방향에 대해 dfs를 실행하면 됩니다. 그리고 겹치는 탐색에 대해서는 자료구조 set을 이용해 중복을 제거했습니다.

 

#include <iostream>
#include <string>
#include <cstring>
#include <set>
using namespace std;
 
char board[5][5];
string num="111111";
set <string> num_set;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
void input(){
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> board[i][j];
}
 
void dfs(int x,int y,int depth) {
    if (depth == 6) { 
        if (num.size() == 6) { num_set.insert(num); }
        return; 
    }
    for (int i = 0; i < 4; i++)
    {
        int nx = dx[i] + x;
        int ny = dy[i] + y;
        if (0 <= nx && nx < 5 && 0 <= ny && ny < 5)
        {
            num[depth] = board[nx][ny];
            dfs(nx, ny, depth + 1);
        }
    }
}
//함수 실행
void run() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            dfs(i, j, 0);
        }
    }
    cout << num_set.size() << '\n';
}
 
void sol() {
    input();
    run();
    //출력확인
    //for (auto i : num_set) cout << i << '\n';
}
int main() {
    sol();
}