[DFS] 2210번 숫자판 점프

2210번 숫자판 점프

 

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

 

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

 

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

 

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

 

예제 입력

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

 

예제 출력

15

 

해결방법

간단한 Brute Force 문제이다

모든 경우를 DFS 탐색을 통해 수행하면된다

 

💎 SET 정리 💎

set 컨테이너는 key의 집합으로 이루어진 컨테이너

 

특징

• iterator로 출력 가능
• 중복을 허용하지 않음
• 값이 insert 되면 자동 정렬

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#define MAX 5
#define INF 987654321
using namespace std;

int map[5][5];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

set<int> s;

void dfs(int x,int y,int cnt,string num){
    if(cnt == 6){
        s.insert(stoi(num));
        return;
    }
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx<0 || nx>=5 || ny<0 || ny>=5) continue;
        
        string tmp = num + to_string(map[nx][ny]);
        dfs(nx,ny,cnt+1,tmp);
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    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 >> map[i][j];
        }
    }
    
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            dfs(i,j,0,"");
        }
    }
    
    cout << (int)s.size() << "\n";
}