백준 2210 - 숫자판 점프 (자바 - 그래프)

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

2210번: 숫자판 점프

 

* 문제 요약

5 x 5 크기의 숫자판이 있다. 각각의 칸에는 숫자 (digit, 0부터 9까지) 가 적혀있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 붙이면 6자리의 숫자가 된다.

이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123 과 같은 수로 만들 수 있다.

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

 

* 입력

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

 

* 출력

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

 

* 예시

 

* 해결 과정

한번 거쳤던 칸을 다시 거쳐도 된다는 조건이 있으므로 2차원 배열에서 이미 방문했는지 아닌지를 확인하기 위한 visited 와 같은 배열은 필요없다.

만들어진 6자리 숫자의 갯수를 구하는데 있어 중복된 것은 허용하면 안되기 때문에 만들어진 숫자를 저장하는 자료구조는 Set 으로 한다.

2차원 배열의 각 인덱스를 기준으로 dfs 탐색을 통해 현재 위치에서 인접해 있는 4방향으로 탐색할 시 만들어 질 수 있는 6자리 숫자를 찾는다.

 

재귀 호출을 수행하는데 있어서 현재 매개변수로 넘겨받은 숫자의 길이가 6자리보다 작다면 미리 만들어둔 dx, dy 배열을 활용해 매개변수로 받은 (i, j) 인덱스로부터 상,하,좌,우 4방향으로 인접해 있는 숫자를 이어붙인 뒤, 해당 방향의 인덱스 (di, dj) 와 이 인덱스 방향에 있는 숫자를 이어붙인 문자열을 매개변수로 재귀호출을 수행해준다.

만약 매개변수로 넘겨받은 숫자의 길이가 정확히 6자리라면 Set 자료구조에 해당 값을 추가해주는 것으로 해당 분기의 재귀 호출을 종료시킨다.

 

이중 반복문을 통해 2차원 배열의 모든 인덱스를 시작점으로 하는 dfs 탐색이 완료되고 나면 Set 자료구조에 저장된 숫자들의 갯수를 출력해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;

public class Main {

    static char[][] graph;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    static Set<String> route = new HashSet<>();

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

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        graph = new char[5][5];

        for (int i = 0; i < 5; i++) {
            String[] inputArray = br.readLine().split(" ");

            for (int j = 0; j < 5; j++) {
                graph[i][j] = inputArray[j].charAt(0);
            }
        }

        String str = "";
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                dfs(i, j, str + graph[i][j]);
            }
        }

        bw.write(route.size() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int ii, int jj, String str) {

        // 여기서 각 요소를 시작점으로 DFS 탐색 후 만들어진 6자리 수 중에서 중복은 배제시킴
        // 중복 배제는 Set 자료구조를 활용하면 됨
        if (str.length() == 6) {
            route.add(str);
        } else {
            for (int i = 0; i < 4; i++) {
                int di = ii + dx[i];
                int dj = jj + dy[i];

                if (di < 0 || di == 5 || dj < 0 || dj == 5) {
                    continue;
                } else {
                    // 반복문을 통해 각 방향을 기준으로 재귀 DFS 탐색 시작
                    dfs(di, dj, str + graph[di][dj]);
                }
            }
        }
    }
}

 

이전에 방문했는지 여부와는 관계없이 탐색을 수행한다는 점만 제외하면 전형적인 2차원 배열에서 깊이가 6이 될 때까지 재귀호출을 수행하면서 4방향으로 인접해있는 인덱스에 대해 탐색을 수행하는 DFS 그래프 탐색문제이다.