BOJ) 숫자판 점프

숫자판 점프

2210번: 숫자판 점프

풀이

 

5x5 크기의 숫자판에서 숫자 6개를 골라, 만들 수 있는 숫자의 갯수를 구하는 문제다.

또한, 000001 or 000000과 같은 숫자가 허용되고 이동할 때는 먼저 거쳐간 칸을 다시 거쳐가도 된다는 조건이 있다.

따라서, int형보다는 String으로 문제를 푸는 것이 적합하다고 생각했고, visit이 필요없는 문제였다.

 

그래서 처음에는 dfs안에서 좌표 for문을 돌면서 각 좌표 상하좌우에 있는 숫자들을 골라 StringBuffer에 붙였다.

하지만, 무한loop가 도는 것을 확인했고, 좌표를 도는 방식이 잘못됐다고 생각했다.

그래서 dfs에서 좌표를 탐색하지 말고, 상하좌우만 옮겨가기로 했다.

 

첫 시작점만 dfs를 처음 시작할 때, 좌표를 넣어주고 StringBuffer에서 remove할 필요 없이 각 시작 좌표마다 StringBuffer를 만들어줬다.

어차피 5x5 숫자판에 불과해서 25개의 StringBuffer만 생성되기 때문이다. ( 메모리 효율이 나쁘지 않음 )

 

6번째 숫자(String)을 붙였을 때, StringBuffer에 있는 문자를 미리 준비한 HashSet에 추가시켜줬다.

중복되는 경우 제거를 편하게 하고, 어차피 만들어진 숫자를 출력하거나 return하는 문제가 아니기 때문에 편하게 Set을 썼다.

모든 좌표에서 dfs가 끝나면 Set에 들어있는 Size가 총 만들 수 있는 숫자의 갯수가 된다.

 

코드

 

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

public class Main {
    final static int DIALSIZE = 5;
    final static int[] dx = {1,-1,0,0}, dy={0,0,1,-1};
    static String[][] dialArr;
    static HashSet<String> numSet;

    public static void main(String[] args) throws IOException {
        setDialArr();
        solution();
    }

    private static void setDialArr() throws IOException {
        dialArr = new String[5][5];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i=0; i<DIALSIZE; i++) {
            dialArr[i] = br.readLine().split(" ");
        }
        br.close();
    }

    private static void solution() {
        numSet = new HashSet<>();
        for(int y=0; y<DIALSIZE; y++) {
            for(int x=0; x<DIALSIZE; x++) {
                dfs(1,x,y,new StringBuffer(dialArr[y][x]));
            }
        }
        System.out.println(numSet.size());
    }

    private static void dfs(int cnt, int x, int y, StringBuffer sb) {
        if(cnt == 6) {
            numSet.add(sb.toString());
            return;
        }

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(isInArea(nx,ny)) {
                sb.append(dialArr[ny][nx]);
                dfs(cnt+1, nx, ny, sb);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }

    private static boolean isInArea(int x, int y) {
        return x>=0 && x<DIALSIZE && y>=0 && y<DIALSIZE;
    }
}