BOJ_2210 / 숫자만 점프

📌 문제 탐색하기

• 입력:
  • 5x5 크기의 숫자판이 주어지며, 각 칸에는 0부터 9까지의 숫자가 적혀 있다.
  • 숫자판은 다섯 줄에 다섯 개의 정수로 주어진다.
• 출력:
  • 숫자판에서 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 출력한다.

---

📌 어떤 알고리즘?

• DFS (깊이 우선 탐색):
  • 각 칸에서 시작하여 상하좌우로 5번 이동하면서 6자리 숫자를 생성하는 모든 경로를 탐색하는 문제로, DFS를 사용하면 쉽게 해결할 수 있다.
  • 5번 이동하여 6자리 숫자가 만들어지면, 이를 Set 자료구조에 저장하여 중복을 제거한다.
• 중복 제거:
  • Set 자료구조를 사용해 6자리 숫자를 저장함으로써 중복 없이 고유한 숫자들의 개수를 쉽게 세는 방법을 사용한다.

---

📌 코드 설계하기

1. 입력 처리:
   • 숫자판을 5x5 배열에 저장한다.
2. DFS 탐색:
   • 각 위치 (i, j) 를 시작점으로 하여 DFS 탐색을 시작한다.
   • 탐색할 때마다 숫자를 이어 붙여 6자리 숫자를 만든다.
   • DFS의 깊이가 6이 되면 Set에 현재 숫자를 추가한다.
3. 상하좌우 이동:
   • 상하좌우 네 방향으로 이동하면서 새로운 위치에서 DFS를 재귀 호출한다.
   • 이동할 때는 5x5 배열의 범위를 넘지 않는지 체크한다.
4. 결과 출력:
   • Set에 저장된 고유한 6자리 숫자의 개수를 출력한다.

---

📌 시도 회차 수정 사항

• 초기 구현:
  • DFS와 상하좌우 이동을 통해 6자리 숫자를 만들고 Set에 추가하는 기본 구현을 완료.
• 수정:
  • DFS에서 StringBuilder 객체를 새로 생성하여 넘기지 않도록 백트래킹을 사용해 마지막 문자를 삭제하는 방식으로 최적화.

---

📌 정답 코드

package BOJ_2210;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class BOJ_2210 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Set<String> uniqueNumbers = new HashSet<>();
    static String[][] digitArr = new String[5][5];
    static int[] dx = new int[]{0, 0, -1, 1};
    static int[] dy = new int[]{1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        for (int i = 0; i < 5; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 5; j++) {
                digitArr[i][j] = st.nextToken();
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                dfs(i, j, new StringBuilder(), 0);
            }
        }
        System.out.println(uniqueNumbers.size());
    }

    public static void dfs(int i, int j, StringBuilder sb, int depth) {
        if (depth == 6) {
            uniqueNumbers.add(sb.toString());
            return;
        }

        sb.append(digitArr[i][j]);

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

            if ((x >= 0) && (x < 5) && (y >= 0) && (y < 5)) {
                dfs(x, y, new StringBuilder(sb), depth + 1);
            }
        }
    }
}

---

📌 시간 복잡도?

• 시간 복잡도
  • 각 칸에서 시작해서 DFS로 5번을 이동하면서, 6자리 숫자를 만드는 모든 경우를 탐색한다.
  • 5x5 배열의 각 칸에서 DFS를 시작하며, 각 DFS는 최대 4^5 (약 1000)개의 경로를 탐색하므로, 최악의 경우 약 25 * 4^5의 경로를 탐색한다.
• 공간 복잡도
  • Set에 고유한 6자리 숫자를 저장하므로, 최대 약 1000개의 고유 숫자를 저장할 수 있다.