[SWEA]#2819 격자판의 숫자 이어 붙이기

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력

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

예제 출력

#1 23

풀이

이 문제는 DFS알고리즘을 이용하면 쉽게 풀 수 있는 문제이다.

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

class Solution {
    static HashSet<Integer> set;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++) {
            map = new int[4][4];
            set = new HashSet<>();
            
            for(int i=0; i<4; i++) {
                String[] input = br.readLine().split(" ");
                for(int j=0; j<4; j++)
                    map[i][j] = Integer.parseInt(input[j]);
            }
            
            for(int i=0; i<4; i++) {
                for(int j=0; j<4; j++)
                    dfs(i, j, 1, map[i][j]);
            }
   
            System.out.println("#"+test_case+" "+set.size());
		}
	}
    
    public static void dfs(int x, int y, int idx, int sum) {
       	if(idx==7) {
            set.add(sum);
            return;
        }
        
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx<0 || nx>=4 || ny<0 || ny>=4) continue;
            
            dfs(nx, ny, idx+1, sum+(int)Math.pow(10, idx)*map[nx][ny]);
        }
    }
}