[BOJ] 백준 2210 숫자판 점프

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

Approach

모든 Case를 비교해야 하므로 완전탐색 유형에 속한다.

완전탐색 기법이란?

5 * 5 칸에 인접한 4가지 방향으로 이동가능하므로

52 × 45 = 25600 에 해당한다.

 

또한 전형적인 DFS 유형 문제이기도 하다

깊이 우선 탐색(depth-first search, DFS)

지나온 칸을 중복해도 상관없으므로 board[][] 범위를 벗어나지 않으면 된다.

지나온 칸이 무엇인지 처리하기 위해 배열과 같은 공간이 필요한데

해당 포스팅에서는 vector와 set을 다루었다.

 

DFS 할 때, 구성된 숫자로 비교하면 되므로

(기존 값 x 10) + (현재 칸)으로 계산한다.

ex) 001023 = 1023

 

▶ Vector 

[C++] [STL] Vector 사용 방법 (Basic)

---

vector

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 5;
const int dx[] = { 0,  0, 1, -1 };
const int dy[] = { 1, -1, 0,  0 };
int board[N][N];

vector<int> vec;

void input()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }
}

void DFS(int x, int y, int val, int cnt) {
    // 6 자리가 채워진 경우
    if (cnt == 6)
    {
        vec.push_back(val);
        return;
    }

    // 인접한 4가지 방향으로 이동
    for (int k = 0; k < 4; k++)
    {
        int nextX = x + dx[k];
        int nextY = y + dy[k];

        if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N)
            continue;

        // (기존 값 * 10) + (현재 위치한 값)
        DFS(nextX, nextY, val * 10 + board[nextX][nextY], cnt + 1);
    }
}


int main() {
    // freopen("input.txt", "r", stdin);
    input();


    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            // 시작위치(x, y), 좌표에 위치한 값, 구성 길이(=1)
            DFS(x, y, board[x][y], 1);
        }
    }


    // 벡터 중복 값 제거
    sort(vec.begin(), vec.end()); // 정렬
    vec.erase(unique(vec.begin(), vec.end()), vec.end()); // 제거

    cout << vec.size() << '\n';
}

 

문제에서 서로 다른 숫자 개수를 찾아야 하므로

vector에서 중복 값을 제거해줘야 한다.

STL 중 set으로도 보다 간결(?)하게 구현 가능하다.

▶ Set 

[C++] [STL] Set

▶ unique 함수 활용한 vector 중복 원소 제거 

[STL] unique 함수 활용한 vector 중복 원소 제거

set

#include <iostream>
#include <set>

using namespace std;

const int N = 5;
const int dx[] = { 0,  0, 1, -1 };
const int dy[] = { 1, -1, 0,  0 };
int board[N][N];

set<int> s; // 중복을 허용하지 않는 set 컨테이너

void input()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }
}

void DFS(int x, int y, int val, int cnt) {
    // 6 자리가 채워진 경우
    if (cnt == 6)
    {
        s.insert(val);
        return;
    }

    // 인접한 4가지 방향으로 이동
    for (int k = 0; k < 4; k++)
    {
        int nextX = x + dx[k];
        int nextY = y + dy[k];

        if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N)
            continue;

        // (기존 값 * 10) + (현재 위치한 값)
        DFS(nextX, nextY, val * 10 + board[nextX][nextY], cnt + 1);
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();

    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            // 시작위치(x, y), 좌표에 위치한 값, 구성 길이(=1)
            DFS(x, y, board[x][y], 1);
        }
    }

    // set이므로 중복값 존재 X
    cout << s.size() << '\n';
}