[백준] 2210 - 숫자판 점프 (C++)

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

5 × 5 크기의 숫자판이 존재하고, 각 칸에는 0부터 9까지의 숫자가 적혀있다. 임의의 칸에서 시작해서, 인접한 네 방향으로 다섯 번 이동하면서 각 칸에 적힌 숫자를 붙여 6자리의 수를 만든다. 만들 수 있는 서로 다른 6자리의 수의 개수를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

가능한 시간 복잡도

• 임의의 시작 위치 선택: 5 × 5
• 인접한 네 방향으로 다섯 번 이동: 4 × 4 × 4 × 4 × 4

 

dfs로 6자리의 수를 모두 찾고, 집합에 저장하는 방식으로 구현해야겠다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. 숫자판 입력 받기
2. 반복문으로 임의의 시작 지점을 골라 dfs 함수에 넣기 + 6자리의 수가 만들어지면 집합에 저장하기
3. 집합 원소 개수 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int board[5][5],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
set<string> s;

void dfs(int x, int y, string chr) {
    if (chr.size() == 6) {
        s.insert(chr);
        return;
    }
    for (int i=0; i<4; i++) {
        int cx=x+dx[i], cy=y+dy[i];
        if (cx<0 || cx>=5 || cy<0 || cy>=5) continue;
        dfs(cx,cy,chr+to_string(board[cx][cy]));
    }
}

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

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

    for (int i=0; i<5; i++)
        for (int j=0; j<5; j++)
            dfs(i,j,to_string(board[i][j]));

    cout << s.size();
}