[백준 - 2210] 숫자판 점프 [C++]

1. 문제

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

2210번: 숫자판 점프

 

2. 풀이과정

6자리 수를 만들 수 있는 모든 경우의 수에 대해 중복을 제거하여 개수를 센다.

 

[코드설명]

dfs함수는 특정 정점을 시작으로 가능한 6자리 수를 모두 만들어준다.

 

safe함수는 해당 정점이 숫자판 범위 안에 있는지 여부를 판별해준다.

 

모든 정점을 시작정점으로 6자리 수를 모두 만들어 보며 set 자료구조에 중복되지 않게 수들을 삽입해주고, set의 크기를 출력해준다. 

 

3. 코드

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

using namespace std;
vector<vector<char>> board;
set<string> nums;
int result;
int dy[4] = {-1, 0, 0, 1}, dx[4] = {0, -1, 1, 0};

bool safe(int y, int x) {
    return (0<=y && y<5) && (0<=x && x<5);
}

void dfs(int y, int x, int depth,vector<char>& num) {
    if(depth == 6) {
        string tmp = "";
        for(int i=0; i<6; i++) tmp += num[i];
        if(nums.find(tmp)==nums.end()) { 
            nums.insert(tmp);
        }
        return;
    }
    for(int i=0; i<4; i++) {
        int ny = y + dy[i], nx = x + dx[i];
        if(safe(ny, nx)) {
            num.push_back(board[ny][nx]);
            dfs(ny, nx, depth+1, num);
            num.pop_back();
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    board.resize(5);
    for(int i=0; i<5; i++) {
        for(int j=0; j<5; j++) {
            char tmp;
            cin >> tmp;
            board[i].push_back(tmp);
        }
    }
    for(int i=0; i<5; i++) {
        for(int j=0; j<5; j++) {
            vector<char> num;
            dfs(i, j, 0, num);
        }
    }
    cout << nums.size();
    return 0;
}