[BOJ] 숫자판 점프

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

Level : S2

유형 : 완전탐색, dfs

---

📌 문제 탐색하기

입력 : 5X5 배열 각 요소 값

 

이 문제는 임의의 위치에서 인접해있는 4 방향으로 5번 움직이는 문제다.

따라서 5*5 총 25개의 인덱스에서 4 방향으로 탐색해야 한다.

 

시간 복잡도를 생각해보면 

임의의 점 선택 : 5*5

선택된 점에서 4 방향으로 5번 움직이는 경우의 수 : 4*4*4*4*4

 

시간복잡도는 O(n^2)이지만 연산 횟수는 25,600번 밖에 되지 않는다.

 

따라서 이 문제는 '완전탐색'으로 진행한다.

 

📌  코드 설계하기

1. 5*5 배열의 값을 입력으로 받는다.

2. 반복문을 돌면서 임의의 점을 택하고 그 점에서 대해 dfs 함수를 실행한다.

3. 재귀를 이용하여 cnt가 5번이 될 때까지 4방향으로 이동하며 나올 수 있는 6자리 수를 만든다.

4. cnt가 5가 되면 map에 만들어진 숫자를 넣고, 함수를 종료한다.

이때 map을 사용하는 이유는 중복된 숫자를 카운트하지 않기 위해서이다.

5. map의 size를 출력하면 만들어진 숫자의 총 갯수가 출력된다.

 

📌  시도 회차 수정 사항

코드를 설계하고 작성한 뒤 돌렸을 때 segmentation fault 오류가 떴다.

이유는 2가지였다.

첫번째는 dfs를 실행할 때 dfs 안에서 반복문을 통해 4가지 방향으로 탐색하는데,

이때 탐색 범위에 대한 제한을 두지 않아 오류가 발생했다.

두번째는 재귀가 종료되면 cnt와 만들어진 수인 s 모두 이전 상태로 돌려야 하는데 cnt를 이전 상태로 돌리지 않아 오류가 발생했다.

 

segmentation fault 오류가 뜨면 배열 범위를 벗어나는 접근을 하는지 꼭! 체크를 해봐야겠다.

 

📌 정답 코드

#include <iostream>
#include <string>
#include <map>
using namespace std;

int arr[7][7], cnt, ret, ny, nx;
string s;
map<string, int> mp;

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

void dfs(int y, int x, int cnt){
    if(cnt == 5){
        mp[s]++;   //map에 넣어서 중복 경우 방지
        return;
    }

    for(int i=0; i<4; i++){
        ny = y + dy[i];
        nx = x + dx[i];

        if(ny<0 || ny>=5 || nx <0 || nx>=5 ) continue;

        s += to_string(arr[ny][nx]);
        dfs(ny, nx, ++cnt); 
        s.pop_back();
        cnt-=1;
    }
}

int main(){

    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            cin >> arr[i][j];
        }
    }

    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            cnt = 0;
            s = to_string(arr[i][j]);
            dfs(i, j, cnt);
        }
    }

    cout << mp.size() << "\n";

    return 0;
}