[코딩테스트] SWEA 2819 격자판의 숫자 이어 붙이기(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 2819 격자판의 숫자 이어붙이기입니다.

포인트

제가 생각한 포인트는 다음과 같습니다.

1. 4X4의 격자
   1. 시작점이 16개
2. 완전탐색 가능성
   1. 총 7개의 길이.
   2. 16 * 4^6 = 2^16의 작업
   3. Java기준 4초 내 가능 => 완전탐색 가능
3. DFS(재귀)를 통한 탐색
   1. 각 칸을 시작점으로 재귀적으로 탐색하여 경로를 구성.
   2. 각 숫자는 중복을 허용하지 않는 점. => HashSet 사용

 

소스코드

package SWExpert.Implementation;

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 Q2819 {
    private static int tc;
    private static int[][] nums;
    private static Set<String> s;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        nums = new int[4][4];

        for (int t = 1; t <= tc; t++) {
            sb.append("#").append(t).append(" ");
            s = new HashSet<>();

            for (int i = 0; i < 4; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 4; j++) {
                    nums[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    findNums(0, i, j, "" + nums[i][j]);
                }
            }
            sb.append(s.size()).append("\n");
        }
        System.out.println(sb);
    }

    public static void findNums(int depth, int x, int y, String num) {
        if (depth == 6) {
            s.add(num);
            return;
        }

        for (int idx = 0; idx < 4; idx++) {
            int nx = x + dx[idx];
            int ny = y + dy[idx];
            if (inRange(nx, ny)) {
                findNums(depth + 1, nx, ny, num + nums[nx][ny]);
            }
        }
    }

    private static boolean inRange(int x, int y) {
        return 0 <= x && x < 4 && 0 <= y && y < 4;
    }
}
/*
1
1 1 1 1
1 1 1 2
1 1 2 1
1 1 1 1
 */

코드 설명

• main 함수
  • BufferedReader와 StringTokenizer를 사용해 빠르게 입력을 처리합니다.
  • 4×4 격자를 2차원 배열 nums에 저장합니다.
  • 격자의 모든 칸을 시작점으로 삼아, (i, j) 위치에서부터 DFS 재귀 함수 findNums를 호출합니다.
• inRange(int x, int y)
  
  • 좌표 (x, y)가 격자 범위(0 이상 4 미만) 내에 있는지 확인하는 함수입니다.
  • 상하좌우로 이동할 때 격자를 벗어나지 않도록 범위 체크에 사용됩니다.
• findNums(int depth, int x, int y, String num)
  재귀 함수, (x, y)를 기준으로 num 선언
  
  • DFS 방식의 재귀 함수입니다.
  • 현재 좌표 (x, y)에서 시작해 문자열 num을 이어 붙이며 탐색합니다.
  • depth == 6이 되면 총 7자리 수가 완성된 것이므로 HashSet에 저장합니다.
  • 상하좌우로 이동하기 위해 dx, dy 배열을 사용하여 다음 위치 (nextX, nextY)를 구하고, 범위 내에 있다면 재귀적으로 계속 탐색합니다.