[JAVA] 백준 2210번 - 숫자판 점프

https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

 

 

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

public class Main{
    static boolean[] visit;
    static int answer;
    static int dx[] = {0,1,0,-1};
    static int dy[] = {1,0,-1,0};
    static int arr[][];

    public static void dfs(int x, int y, int num, int depth){
        if(depth == 6) {
            if(!visit[num]){
                visit[num] = true;
                answer++;
            }
            return;
        }
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                int nx = x+dx[i];
                int ny = y+dy[i];

                if(nx>=0 && ny >=0 && nx<=4 && ny<=4) {
                    dfs(nx, ny, num * 10 + arr[nx][ny], depth+1);
                }
            }
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        arr = new int[5][5];
        visit = new boolean[1000000];
        for(int i=0; i<5; i++){
            st= new StringTokenizer(br.readLine());
            for(int j=0; j<5; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                dfs(i, j, arr[i][j], 1);
            }
        }
        System.out.println(answer);
    }
}

 

모든 정점에서 네 방향으로 뻗어나가면서 만들어질 수 있는 모든 6자리수를 구하는 문제이다. 

 

정점을 거칠때마다 num을 더해주고, dept를 1씩 증가시켜 6이 되었을 때 중복되지 않은 num이면 answer을 누적시켜 카운팅한다.