[JAVA] 백준 2210_숫자판점프

[문제링크]

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

 

📌 문제 탐색하기

25칸으로 이루어진 숫자판에서 한번 탐색 시 6개의 숫자열을 만들어내고 , 이 숫자판에서 만들 수 있는 6개 숫자열의 모든 경우의 수를 출력하는 문제이다. ( 중복되는 동일한 숫자열은 제외한다. )

 

📌 가능한 시간복잡도 

가능한 시간복잡도를 생각해보면 숫자판의 모든 위치에서 시작 가능하기 때문에 25개의 모든 칸 탐색.

이때 각각 탐색에서 6개의 숫자를 만들도록 5번 이동한다. 이동시 4가지 방향으로 이동이 가능하다. 

정리 ) 각각 칸마다 5번 이동하면서 이동시 4개의 선택지를 가지고 있으므로 한칸에서 최대 4의 5승 즉 1024번의 탐색이 가능하다. 25칸을 가진 숫자판에서 탐색을 시작하므로 가능한 시간복잡도는 O(25 * 1024)입니다. 

 

📌 코드 설계하기

1. 우선 5x5의 숫자판의 모양을 가지는 배열을 만들어준다.

2. 모든 칸에서 DFS를 사용해서 6자리 숫자를 만든다. 

3. 중복된 숫자는 제거한 만들 수 있는 최종 개수 출력한다.

 

📌 정답 코드

import java.util.*;

public class Main {
    static int[][] board = new int[5][5];
    static Set<String> uniqueNumbers = new HashSet<>();
    static int[] dx = {-1, 1, 0, 0}; 
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        
       
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                dfs(i, j, "", 0);
            }
        }
        
        System.out.println(uniqueNumbers.size());
    }

    static void dfs(int x, int y, String num, int depth) {
        if (depth == 6) {
            uniqueNumbers.add(num);
            return;
        }
        
        num += board[x][y]; 
        
       
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) { 
                dfs(nx, ny, num, depth + 1);
            }
        }
    }
}