[백준 BOJ] 2210번 숫자판 점프 (C++/cpp)

문제 설명

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

 

 

접근 방법 - DFS를 활용한 브루트포스 알고리즘 문제

백준의 2210번 문제는 브루트포스 알고리즘과 깊이 우선 탐색(DFS)을 함께 응용하여 해결할 수 있는 문제이다.

해당 문제는, 5*5 숫자판에 대하여 만들 수 있는 6자리 숫자의 가짓수를 구하여 정답으로 출력해야 하는 문제이다.

이 문제의 지문에는 "한번 거쳤던 칸을 다시 거쳐도 된다"는 전제가 있기 때문에, 다른 DFS 문제보다도 비교적 쉬운 축에 속한다고 볼 수 있다. (이 지문을 통하여 각 요소의 방문 여부를 따져줄 필요는 없게 되었다.)

시간제한도 2초로 넉넉하며 입력으로 주어지는 숫자도 총 25개뿐이기 때문에, 필자는 재귀 함수를 통하여 가능한 경우의 수를 모두 구하여서 서로 다른 가짓수를 수시로 파악해 보았다.

자세한 설명은 아래에 마저 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 아래와 같이 전역 변수를 미리 선언해 둔다.

- 5*5 숫자판의 정보를 저장할 배열 number를 선언해 둔다.

(실질적인 입력값은 (1,1)부터 (5,5)까지 저장할 예정이며, 그 이외는 모두 NULL값으로 두어 연산을 수행할 예정이다.)

- 만들 수 있는 서로 다른 6자리 숫자 정보들을 저장할 벡터 v를 선언해 둔다.

- 숫자 만들기를 하면서 숫자판 상 상/하/좌/우로 이동할 때 활용한 loca 배열을 {{0,0,1,-1}, {1,-1,0,0}}로 설정해 둔다.

<< 이때 숫자 조합 및 요소 삽입을 더욱 원활히 하기 위하여, number와 v는 각각 char형, string형으로 지정하였다. >>

 

2) 5*5 숫자판의 정보를 입력받아, 하나씩 number에 저장하도록 한다.

 

3) 각 25개의 숫자를 시작으로 하여, makeNum() 함수를 통해 아래 연산을 수행하며 숫자 만들기를 진행한다.

(이때, makeNum()의 매개변수 구성은 (탐색할 요소의 행 번호, 탐색할 요소의 열 번호, 만들고 있는 숫자의 상태)을 뜻한다.)

- 임의의 변수 s에 현재 위치의 number 요소를 삽입한다.

- loca 배열의 값을 하나씩 순회하고 이를 통해 다음으로 이동할 좌표 값을 loca_x와 loca_y에 각각 저장한다.

이동할 좌표에 NULL값이 저장된 것이 아니라면, 이는 실질적인 숫자판의 정보임을 뜻하기 때문에 이에 대하여 재귀를 수행한다.

- 위와 같이 재귀를 통한 숫자 만들기를 수행하다가, s의 길이가 6이 되는 순간이 온다면 완성된 s값이 v에 존재하는지를 파악한다.

만약 v에 현재 s값이 없다면, 해당되는 s값을 v에 삽입하여 숫자의 가짓수에 포함하고 함수의 실행을 종료한다.

 

4) 3)에서 가능한 조합의 수를 모두 파악해 보았다면, v의 크기가 곧 만들 수 있는 숫자의 총 가짓수를 의미하게 된다.

따라서, 현재 v의 크기를 정답을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 2210번 코드
char number[7][7];
vector<string> v;
int loca[2][4] = { {0,0,1,-1}, {1,-1,0,0} };

void makeNum(int x, int y, string s) {
    if (s.length() == 6) {
        if (find(v.begin(), v.end(), s) == v.end()) {
            v.push_back(s);
        }
        return;
    }
    s += number[x][y];

    for (int i = 0; i < 4; i++) {
        int loca_x = x + loca[0][i];
        int loca_y = y + loca[1][i];
        if (number[loca_x][loca_y] != NULL) {
            makeNum(loca_x, loca_y, s);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);
    
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            cin >> number[i][j];
        }
    }

    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            makeNum(i, j, "");
        }
    }

    cout << v.size() << endl;
}

 

제출 결과

(2023.05.28 백준 2210번 문제 제출 결과)