[백준] 2210 숫자판 점프 자바(Java)

문제설명

×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

 

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

 

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

 

풀이

dfs알고리즘을 사용해서 풀이했다. 상, 하, 좌, 우 방향으로 가면서 문자열은 더해주고 카운트는 증가 시킨다.

카운트가 5라면 set에 더해주고 return 한다. 서로 다른 여섯 자리의 수임으로 set을 사용해서 넣어주었다.

 

통과한 코드 ✅

import java.io.*;
import java.util.*;

public class Main {
    public static int n = 5;
    public static String map[][] = new String[n][n];
    public static boolean visited[][] = new boolean[n][n];
    public static int dx[] = {1, -1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};
    public static Set<String> set = new HashSet<>();

    // 아래는 테스트케이스 출력을 해보기 위한 코드입니다. 아래에는 잘못된 부분이 없으니, 위의 코드만 수정하세요.
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            String strArr[] = str.split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = strArr[j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dfs(i, j, 0,map[i][j]);

            }
        }

        System.out.println(set.size());
    }

    public static void dfs(int x, int y, int cnt, String s) {
        if(cnt==5){
            set.add(s);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int cx = x + dx[i];
            int cy = y + dy[i];

            if (cx >= 0 && cy >= 0 && cx < n && cy < n) {
                if (!visited[cx][cy]) {
                    dfs(cx, cy, cnt+1,s+map[cx][cy]);
                }
            }
        }
    }
}