[C/C++] 백준 #2210 숫자판 점프(집합, 백트래킹)

#2210은 실버 문제로 난이도는 높지 않습니다.  백트래킹 알고리즘을 이용해서 모든 경우의 수를 찾아내었고, 집합을 이용해서 중복을 제거해서 풀었습니다.

 

문제 링크입니다.

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

2210번: 숫자판 점프

 

기본적으로 2차원 배열에서 백트래킹은 경계조건하고 상하좌우 움직임 등만 잘 처리하면 큰 무리가 없습니다.

 

 

집합 자료구조는 C++에서 제공하는 것이 두가지인데, 일반 집합 자료구조는 set이라고 하며, 이 자료구조는 이진트리를 이용합니다.  그래서 정렬이 된다는 특징이 있습니다.  unordered set 집합 자료구조는 해시테이블을 이용합니다.  자료의 개수가 많다면, 정렬되지 않는 집합 자료구조인 unordered set을 이용하는 것이 좋습니다.  정렬 구조인 경우에는 \(O(\log N)\)의 시간복잡도를 갖지만 해시 테이블을 사용하는 경우에는 상수시간 시간 복잡도를 갖습니다.  하지만 나올 수 있는 숫자들이 크지 않기 때문에 어떤 자료구조를 사용해도 괜찮습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2210
//        - by Aubrey Choi
//        - created at 2019-07-22
//------------------------------------------------
#include <stdio.h>
#include <unordered_set>
std::unordered_set<int> set;
char map[5][5];

void trav(int r, int c, int s, int v)
{
    v += map[r][c]*s;
    if(s == 1)
    {
        set.insert(v);
        return;
    }
    int d[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
    for(int i = 0; i < 4; i++)
    {
        int nr = r+d[i][0], nc = c+d[i][1];
        if(nr < 0 || nr >=5 || nc < 0 || nc >= 5) continue;
        trav(nr, nc, s/10, v);
    }
}

int main()
{
    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            int s;
            scanf("%d", &s);
            map[i][j] = s;
        }
    }
    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
            trav(i, j, 100000, 0);
    }
    printf("%lu\n", set.size());
}