[백준][BOJ 2210] - 숫자판 점프

문제

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

2210번: 숫자판 점프

문제 접근

• 숫자판의 임의의 위치에서 인접한 4방향으로 5번 이동하면서 숫자판에 적힌 숫자를 붙이는 것이 핵심적인 기능이다.
  • 이동 시에 이미 방문했던 칸을 다시 방문해도 상관없다는 조건이 붙어 있다.
  • 숫자가 0인 경우에도 0으로 시작하는 수를 만들 수 있다.
• 위의 규칙을 만족시키면서 숫자판에서 이동할 때 나올 수 있는 모든 숫자의 개수를 구하는 것이 문제에서 요구하는 내용이다.
• 숫자판의 임의의 위치에서 시작하므로 나올 수 있는 모든 숫자의 개수를 구하기 위해서는 5 X 5 크기의 모든 숫자판을 시작점으로 두어 위의 핵심 기능을 수행하도록 하는 것이 해법이다.
• 핵심 기능을 구현하는 것은 재귀를 활용해서 구현할 수 있으며 DFS 방법을 사용할 수 있다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

  static String[][] board;
  static int[] dx = {0, 0, 1, -1};
  static int[] dy = {1, -1, 0, 0};
  static Set<String> answer;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    board = new String[5][5];
    answer = new HashSet<>();

    for (int i = 0; i < 5; i++){
      StringTokenizer st = new StringTokenizer(br.readLine());

      for (int j = 0; j < 5; j++){
        board[i][j] = st.nextToken();
      }
    }

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

    System.out.println(answer.size());
  }

  public static void dfs(int y, int x, String currentString, int moveCount){
    if (moveCount == 5){
      answer.add(currentString);
      return;
    }

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

      if (ny < 0 || ny >= 5 || nx < 0 || nx >= 5){
        continue;
      }

      dfs(ny, nx, currentString + board[ny][nx], moveCount + 1);
    }
  }
}