<Algorithm> 70. 2819번 격자판의 숫자 이어붙이기(SW Expert)

1. 2819번 격자판의 숫자 이어붙이기

• 어렵게 느껴졌던 문제, 백준만 풀다가 한번 SW Expert 문제를 풀어봤는데 익숙하지 않아서 인지 어렵게 느껴졌다.

• 단순히 DFS로 모든 경우를 탐색하니 통과가 되었다. 4 * 4 행렬로 고정 되었기 때문이라 생각한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static int[][] arr;
    static boolean[][] visited;
    static boolean[] checkNumber;
    static int count;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        ArrayList<String> ans = new ArrayList<>();
        
        for(int c = 0; c < T; c ++) {
            count = 0;
            arr = new int[4][4];
            visited = new boolean[4][4];
            checkNumber = new boolean[10000000];
            StringTokenizer st;
            
            for(int i = 0; i < 4; i ++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < 4; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            for(int i = 0; i < 4; i ++) {
                for(int j = 0; j < 4; j ++) {
                    dfs(i, j, "");
                }
            }
            ans.add("#"+(c+1)+" "+count);
        }
        
        for(String str : ans)
            System.out.println(str);
        
    }
    private static void dfs(int x, int y, String std) {
        
        std += arr[x][y];
        
        if(std.length() == 7) {
            //System.out.println(std);
            
            if(!checkNumber[Integer.parseInt(std)]) {
                checkNumber[Integer.parseInt(std)] = true;
                count++;
            }
            
            return;
        }
        
        
        int[] dx = {0 , 0, 1, -1};
        int[] dy = {1 , -1, 0, 0};
        
        for(int i = 0; i < 4; i ++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && ny >= 0 && nx < 4 && ny < 4) {
                    dfs(nx, ny, std);                    
            }
            
        }
        
    }
}

참고 & 출처