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

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

문제 출처 : 링크

4x4 말판에 0~9까지 임의의 수가 작성된다.

지나온 말판도 다시 지나갈 수 있는 것이 포인트. dfs로 접근하는데 방문하는 부분을 따로 지정하지 않으면 될 것 같다.

말판에서 총 6번 움직이면서 (처음에 시작하는 지점 포함) 총 7자리의 수가 만들어지면 저장한다

이때 모든 경우의 수를 진행하면서, 중복되는 부분은 없애고 총 몇 가지 수를 만들 수 있는 지 구해야하는 문제다.

숫자를 int로 만들지 않고, 그냥 문자열로 받아서 저장하는 방식으로 접근했다.

HashSet에 저장하면, 중복되는 부분은 추가로 저장하지 않으므로 이 문제에서 사용하면 좋을 것 같아서 적용해봤다.

만약 ArrayList나 배열을 사용한다면, 저장 전에 조건문을 통해 중복 부분을 체크해줘야겠지만 HashSet은 알아서 중복을 걸러주기 때문에 그럴 필요가 없다.

마지막으로 해당 HashSet의 size를 출력해주면, 총 만들 수 있는 개수가 나오게 될 것이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Solution2819 {
    
    static String[][] map;
    static HashSet<String> set; // 중복을 저장하지 않기 위한 HashSet
    
    static int dx[] = {0, 0, -1, 1};
    static int dy[] = {-1, 1, 0, 0};
 
    public static void dfs(int x, int y, int cnt, String str){
        
        if(cnt == 7) { // 7개 채우면 hashset에 저장 후 return
            set.add(str);
            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; // 배열 밖으로 벗어나면 continue
            else {
                dfs(nx, ny, cnt+1, str+map[nx][ny]); // cnt 늘리고, str에 해당 수 추가
            }
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int ts = Integer.parseInt(st.nextToken());
        set = new HashSet<String>();
        
        for (int t = 1; t <= ts ; t++) {
            
            map = new String[4][4];
            set.clear(); // 다음 테스트 케이스를 위해 hashset 비워주기
            
            for (int i = 0; i < 4; i++) {
                st = new StringTokenizer(br.readLine(), " ");                
                for (int j = 0; j < 4; j++) {
                    map[i][j] = st.nextToken();
                }
            }
            
            
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    String str = map[i][j]; // 첫번째 값 저장
                    dfs(i, j, 1, str);
                }
            }
            
            System.out.println("#"+t+ " " + set.size());
        }
    }
 
}