[SW Expert] 2819. 격자판의 숫자 이어 붙이기

1) 생각

4 x 4 격자 판이 주어졌을 때, 7개를 탐색했을 경우 나올 수 있는 숫자의 개수를 구하시오(중복 비허용)

처음 생각

우선 4 x 4이고 시간도 Java의 경우 4초를 주기때문에 충분히 완전탐색으로 해결할 수 있다고 생각하였다.

따라서 DFS를 이용하여 탐색을 진행하였다.

다음 생각

DFS를 진행하면서 7개의 탐색을 진행하면 방문 배열을 통하여 이미 온곳이면 return하고 방문하지 않았던 곳이면 방문표시를 한 뒤, 개수 변수를 result++ 해준 뒤, return 처리를 하였다. 알고리즘을 다 완성하고 나서 보니 HashSet 자료구조를 쓰는것이 더 좋을 것 같아 수정하였다.

다음 생각

HashSet의 제너릭 타입을 String으로 해주었는데 아무래도 객체들을 다루다보니 속도가 느리고 메모리를 많이 잡아 먹었다.

2) 방안

1) HashSet 자료구의 경우 내부에 보따리에 중복을 허용하지 않고 집어넣는다고 표현하면 좋을 것 같다. 순서는 없지만(Interator를 통해 만들어 줄 수는 있다.) 중복을 허용하지 않아 마지막에 HashSet의 size를 통해 결과를 간단히 출력할 수 있었고 이전에 비해서 방문처리 같은게 필요하지 않으므로 시간과 메모리가 좀 더 빨라지고 적어졌다.

2) 결국 해당 숫자를 만들 수 있냐의 문제이기 때문에 맨 앞에 0이 있던 아니던 같은 숫자가 만들어질 것이다. HashSet의 제너릭 타입을 Integer로 바꾸니 속도와 메모리가 2배 정도 향상됐다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Solution {
    static int[][] arr;
    static HashSet<Integer> result;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        result = new HashSet();
        for(int i=1;i<=tc;i++){
            result.clear();
            arr = new int[4][4];
            for(int j=0;j<4;j++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int k=0;k<4;k++)
                    arr[j][k] = Integer.parseInt(st.nextToken());
            }
            for(int j=0;j<4;j++)
                for(int k=0;k<4;k++)
                    solve(j,k,1,arr[j][k]);
            System.out.println("#"+i+" "+result.size());
        }
    }
    
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static void solve(int x,int y,int cnt,int n){
        if(cnt==7){
            result.add(n);
            return;
        }        
        for(int i=0;i<4;i++){
            int tx = x+dir[i][0];
            int ty = y+dir[i][1];
            if(tx<0 || ty<0 || tx>=4 || ty>=4) continue;
            solve(tx,ty,cnt+1,(n*10)+arr[tx][ty]);
        }
    }
}