[BOJ 2210] 숫자판 점프

문제 설명

2210번: 숫자판 점프

 

예제에 하이라이트를 추가하여 좀 더 보기 쉽게 정리하면 아래와 같다.

이렇게 하여 만들 수 있는 서로 다른 여섯 자리의 개수를 구하면 된다.

 

어떤 알고리즘을 사용해야 할까?

• 정사각형 모양의 숫자판
• 인접한 네 방향으로 이동

한다는 점에서 그래프 탐색 알고리즘을 사용해야 한다고 생각하였다.

 

그리고 여섯 자리 수를 만들기 위해 깊숙이 들어가기 때문에 BFS(너비 우선 탐색)이 아닌 DFS(깊이 우선 탐색)을 사용해야 한다고 생각하였다.

 

DFS 간단 정리

DFS Visualize

DFS는 임의의 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

 

DFS는 재귀와 스택 2가지 방법으로 구현할 수 있다.

 

재귀

로직을 수도코드로 나타내면 아래와 같다.

DFS(u, adj)
    u.visited = true // 1. 현재 위치한 정점 u를 방문 처리해준다.
    for each v ∈ adj[u] // 2. 인접한 노드들 중
        if v.visited == false // 3. 방문하지 않은 노드가 있다면
            DFS(v, adj) // 4. 재귀적으로 탐색을 진행한다.

이를 C++ 코드로 작성하면 아래와 같다. 참고로, 아래 코드는 인접 행렬일 경우의 DFS 코드이다.

void dfs(int u){
    visited[u] = 1; // 1. 현재 위치한 정점 u를 방문 처리해준다.
    cout << u << "\n";
    
    for(int v : adj[u]){ // 2. 인접한 노드들 중
        if(visited[v] == 0){ // 3. 방문하지 않은 노드가 있다면
            dfs(v); // 4. 재귀적으로 탐색을 진행한다.
        } 
    }   
    return; 
}

 

스택

출처: https://www.codesdope.com/course/algorithms-dfs/

1. 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 최상단 노드(top)에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.(pop)
3. 2번의 과정을 더 수행할 수 없을 때까지 방문한다. (while문 활용)

void dfs(vector<vector<int>> adj, int start) {
    int n = adj.size();
    vector<int> visited(n, 0);
    stack<int> s;

    s.push(start); // 시작 노드를 스택에 삽입

    while (!s.empty()) { // 스택이 빌 때까지 반복
        int u = s.top();
        s.pop();

        if (visited[u] == 0) {
            visited[u] = 1;
            cout << u << "\n";
        }

        for (int v : adj[u]) {
            if (visited[v] == 0) {
                s.push(v);
            }
        }
    }
}

 

구현 아이디어

• 재귀의 종료 조건 = 6자리의 수가 됐을 때 = 6칸 이동했을 때
  • 몇 칸 이동했는지 count할 변수 필요
• 한 번 거쳤던 칸은 다시 거쳐도 됨 = 방문 여부를 확인하는 배열은 없어도 되겠다
• 서로 다른 수의 개수를 구해야 됨 = 중복은 하나로 처리 = set 자료 구조를 사용하자
• 수를 저장할 때 string이나 추가적인 배열을 사용하지 말고 x10 연산을 통해 숫자를 왼쪽으로 한칸씩 밀어주자
  • ex) 111112 = 11110 + 2 = 1111 * 10 + 2

 

문제 풀이

#include <iostream>
#include <set>

using namespace std;

int map[5][5];
set<int> s;

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

// x, y: 좌표
// num: 현재까지 만든 수
// len: 현재까지 만든 수의 길이
void DFS(int x, int y, int num, int len) {
    if (len == 6) { // 재귀 종료
        s.insert(num);
        return;
    }

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

        if (nx >=0 && nx < 5 && ny >=0 && ny < 5) { // 다음 칸이 숫자판 내부에 존재할 때
            DFS(nx, ny, num * 10 + map[nx][ny], len + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 입력
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            cin >> map[i][j];
        }
    }

    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            DFS(i, j, map[i][j], 1);
        }
    }

    cout << s.size() << '\n';

    return 0;
}