[DFS] 백준 2210번 - 숫자판 점프

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

2210번: 숫자판 점프

백준 DFS 문제다.

set 컨테이너를 활용해 풀면 쉽게 풀 수 있다.

갈 수 있는 방향으로 중복허용해 5번 이동하여 만들 수 있는 문자열의 개수를 출력하는 문제다.

 

#include <set>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int max_answer = -1;
vector<vector<string> > map;
set<string> s;
 
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
 
void dfs(int jumpcnt, string val, int r, int c){
    if (jumpcnt == 5){
        s.insert(val);
        return;
    }
    for (int i = 0; i < 4; i++){
        int nr = r + direction[i].dr;
        int nc = c + direction[i].dc;
        if (0 <= nr && nr < 5 && 0 <= nc && nc < 5){
            dfs(jumpcnt + 1, val + map[nr][nc], nr, nc);
        }
    }
}
 
int main(){
    map.assign(5, vector<string>(5, ""));
    for (int i = 0; i < 5; i++){
        for (int j = 0; j < 5; j++){
            int ele;
            cin >> ele;
            map[i][j] = map[i][j] + to_string(ele);
        }
    }
    for (int i = 0; i < 5; i++){
        for (int j = 0; j < 5; j++){
            dfs(0, map[i][j], i, j);
        }
    }
    cout << s.size() << '\n';
    return 0;
}