[BOJ] 2210 숫자판 점프 - JAVA

1. 문제

2210번: 숫자판 점프

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

---

2. 풀이

방문체크 없이 depth 6까지 전부 dfs하면 된다.

중복을 거르는 용도로 set을 사용했다.

import java.io.*;
import java.util.*;

public class BOJ_2210_숫자판점프 {
   static int[][] board = new int[5][5];
   static int[] number = new int[6];
   static int[][] delta = {{1,0},{-1,0},{0,1},{0,-1}};
   static Set<String> set = new HashSet<>();
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      for(int i=0;i<5;i++){
         st = new StringTokenizer(in.readLine());
         for(int j=0;j<5;j++){
            board[i][j] = Integer.parseInt(st.nextToken());
         }
      }

      for(int i=0;i<5;i++){
         for(int j=0;j<5;j++){
            find(i,j,0);
         }
      }

      System.out.println(set.size());
   }
   public static void find(int i,int j,int cnt){
      if(cnt==6){
         StringBuilder num = new StringBuilder();
         for(int n:number){
            num.append(n);
         }
         set.add(num.toString());
         return;
      }

      number[cnt] = board[i][j];

      for(int d=0;d<4;d++){
         int ni = i+delta[d][0];
         int nj = j+delta[d][1];
         if(ni<0 || nj<0 || ni>=5 || nj>=5) continue;
         find(ni,nj,cnt+1);
      }

   }
}

---

3. 결과