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 1 2 1
1 1 1 1 1

• 예제 출력 1

15

Solution

#include <iostream>
#include <set>

using namespace std;

int MATRIX[6][6];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
set <int> result;

void DFS(int X, int Y, int data, int count){
    if(count == 5) {
        result.insert(data);
        return;
    }
    for(int i = 0; i < 4; i++){
        int nx = X + dx[i];
        int ny = Y + dy[i];
        if(nx >= 1 && nx <= 5 && ny >= 1 && ny <= 5){
            DFS(nx, ny, data * 10 + MATRIX[nx][ny], count + 1);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 1; i <= 5; i++){
        for(int j = 1; j <= 5; j++) cin >> MATRIX[i][j];
    }
    for(int i = 1; i <= 5; i++){
        for(int j = 1; j <= 5; j++) DFS(i, j, MATRIX[i][j], 0);
    }
    cout << result.size() << '\n';
}

DFS, 그리고 Set의 특징을 이용한 문제다.
처음엔 BFS를 사용해서 풀려고 했지만, 루프에 빠져버린 건가...오래걸렸다.
반드시 큐에 데이터를 저장해야 할 이유가 있는 문제는 아니었다. 그리고 DFS를 써야하는 이유가 있다면 6번만 탐색한다는 제약조건이 있었기에 굳이 BFS를 쓸 필요는 없었다.

int MATRIX[6][6];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
set <int> result;

void DFS(int X, int Y, int data, int count){
    if(count == 5) {
        result.insert(data);
        return;
    }
    for(int i = 0; i < 4; i++){
        int nx = X + dx[i];
        int ny = Y + dy[i];
        if(nx >= 1 && nx <= 5 && ny >= 1 && ny <= 5){
            DFS(nx, ny, data * 10 + MATRIX[nx][ny], count + 1);
        }
    }
}

DFS긴 하지만 BFS 마냥 각 방향의 경우마다 탐색을 진행한다. 그리고 탐색을 진행하면서 자릿수를 하나하나 올리며 데이터를 쌓아 올려간다.

최종적으로 탐색을 끝냈을 때 set에 저장함으로써 중복을 자동으로 제거하며 가능한 모든 경우를 구할 수 있다.