[SWEA] 2819. 격자판의 숫자 이어 붙이기 (D4) (Java)

[SWEA] 2819. 격자판의 숫자 이어 붙이기 (D4) (Java)

Problem

제출일 : 2020-02-18

문제 풀이 시간 : 15M

난이도 : ★

---

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.

격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.

이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.

단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.

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

input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 4개의 줄에 걸쳐서, 각 줄마다 4개의 정수로 격자판의 정보가 주어진다.

Output

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 격자판을 이동하며 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.

Example

input

1
1 1 1 1
1 1 1 2
1 1 2 1
1 1 1 1

output

#1 23

Solution & Inpression

방문 처리를 하지 않고 6번까지 깊이 우선탐색후 HashSet 자료구조를 사용하여 중복을 제거하고 size를 출력하였다.

Code

언어 : JAVA

메모리 : 57,648 kb

실행시간 : 224 ms

import java.util.HashSet;
import java.util.Scanner;

class Solution {
    static int T, N;
    static HashSet<String> set;
    static int[][] map;

    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        N = 4;

        for (int tc = 1; tc <= T; tc++) {
            map = new int[4][4];
            set = new HashSet<>();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    DFS(i, j, 0, "" + map[i][j]);
                }
            }
            System.out.println("#" + tc + " " + set.size());

        } // end of TC
    }

    private static void DFS(int i, int j, int depth, String str) {
        if (depth == 6) {
            set.add(str);
            return;
        }
        for (int dir = 0; dir < dc.length; dir++) {
            int r = i + dr[dir];
            int c = j + dc[dir];
            if (isRange(r, c)) {
                DFS(r, c, depth + 1, str + map[r][c]);
            }
        }
    }

    private static boolean isRange(int r, int c) {
        if (0 <= r && r < 4 && 0 <= c && c < 4)
            return true;
        return false;
    }
}