BOJ 2210 숫자판 점프 (Java)

문제 탐색하기

• 배열 형태 2차원 배열 그래프 탐색 문제이고, 4가지 방향을 따라 탐색하므로 DFS를 사용할 것이다.
• 방문 노드를 검사하지 않는다.

• 서로 다른 6자리 수를 만들면 된다.

• 5 X 5 배열 내에서 이동 가능한 방향은 4가지이고, 최대 6번 이동할 수 있으므로 최악의 경우에도 탐색 횟수가 5 X 5 X (4 ^ (6 - 1)) = 25,600 으로 크지 않다.
• 따라서 이 문제는 완전탐색 (DFS) 방식으로 풀이가 가능하다.

코드 설계하기

• 숫자 판을 배열 형태로 저장한다.
• 전체 판에 대해 4가지 방향으로 DFS를 수행한다.
  • 깊이가 5가 되거나 / 숫자의 길이가 6이 되면 종료한다. (6번 이동)
  • 숫자를 StringBuilder 로 만들어 길이가 6이 되면 종료 후 answer 자료구조에 저장한다.
  • 판을 넘어가지 않는 유효한 이동인지 검사가 필요하다.
• 중복을 허용하지 않으므로 Set 자료구조 컬렉션에 저장 후, size()를 정답으로 출력한다.

정답 코드 (Java)

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
import java.util.HashSet;  
import java.util.StringTokenizer;  
  
public class b2210 {  
    private static int[][] map = new int[5][5];  
    private static int N = 5;  
    private static HashSet<String> ans = new HashSet<>(); // 정답을 저장한다.  
    private static int[] dx = {-1, 0, 1, 0};  
    private static int[] dy = {0, -1, 0, 1};  
  
    public static void main(String[] args) throws Exception{  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        for (int i = 0; i < N; i++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            for (int j = 0; j < N; j++) {  
                map[i][j] = Integer.parseInt(st.nextToken());  
            }  
        }  
  
        // 전체 map에 대해 DFS 수행  
        for (int i = 0; i < N; i++) {  
            for (int j = 0; j < N; j++) {  
                dfs(i, j, new StringBuilder().append(map[i][j]));  
            }  
        }  
  
        System.out.println(ans.size());  
    }  
  
    private static void dfs(int i, int j, StringBuilder sb) {  
        // 종료 조건: 길이가 6이면 set에 추가 후 종료  
        if (sb.length() == 6) {  
            ans.add(sb.toString());  
            return;  
        }  
  
        // 4방향 탐색  
        for (int k = 0; k < 4; k++) {  
            int n = i + dx[k];  
            int m = j + dy[k];  
  
            if (checkMap(n, m)) continue;  
  
            // 현재 숫자 추가  
            sb.append(map[n][m]);  
            dfs(n, m, sb);  
            // 탐색 후 마지막 문자 제거  
            sb.deleteCharAt(sb.length() - 1);  
        }  
    }  
  
    private static boolean checkMap(int n, int m) {  
        return n < 0 || n >= N || m < 0 || m >= N;  
    }  
}