[ 백준 - 2210 ] 숫자판 점프

난이도 : S2

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

Tag : BFS

 

문제 탐색하기 

- 인접해 있는 네 방향으로 5섯 번 이동하면서 숫자를 차례대로 붙이면 되는 문제였습니다.

- 이전에 방문했던 칸을 다시 방문 해도 됨. 

- 서로 다른 여섯 자리의 수들의 개수를 구해야함. 중복 X

시도 1 (성공😲)

 

시간복잡도

방문 했던 칸을 다시 방문해도 되기때문에 특정 칸에서 시작했을경우 이동할 수 있는 최대 4방향으로 이동할 수 있습니다.

그러므로 5번이동했을 때의 경우의 수는 4^5 = 1024 입니다. 시작칸은 총 25가지 이기 때문에 총 경우의 수는 1024 * 25 = 25,600 으로 제한 시간 2초안에 여유롭습니다. 그렇기 때문에 모든 경우를 탐색하여 해결할 수 있는 문제입니다.

선택 알고리즘

항상 4가지 방향으로 이동할 수 있기 때문에 재귀 함수를 활용한 완전탐색과 DFS를 통해 해결하고자 합니다.

 

구현 방법

1. 값을 입력받는다.

2. dfs를 구현한다.

2-1. 종료조건 : 6번 이동째에 종료. 이어지는 문자열을 집합에 넣는다. 

2-2. 각 4가지 방향으로 이동하도록 재귀 호출

전체코드

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

class Main {

    private static int[][] board = new int[5][5];
    private static Set<String> cases = new HashSet<>();
    private static int[] dirX = { 1, 0, -1, 0 };
    private static int[] dirY = { 0, 1, 0, -1 };

    public static void dfs(String s, int x, int y) {
        
        if (s.length() == 6) {
            cases.add(s);
            return;
        }

        if (x < 0 || x >= 5 || y < 0 || y >= 5) {
            return;
        }
        
        for (int dir = 0; dir < 4; dir++) {
            bfs(s + board[y][x], x + dirX[dir], y + dirY[dir]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for (int i = 0; i < 5; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                bfs("", i, j);
            }
        }
        System.out.println(cases.size());

    }
}

 

204ms가 소모되었으며 여유롭게 통과 하였습니다.

 

마무리

각 모든 점의 bfs를 수행하였습니다. 방문했던 곳은 다시 방문하지 않는다등 조건이 추가되면 난이도가 올라갈 수 있을것 같습니다.

재귀 함수를 구현할 때에는 basecondition을 생각해야하며, 어떤 인자들을 다음으로 넘길지에 대해 고민해야 할 것 같습니다.

이번 문제에서는 처음에 depth를 함께 넣어주었지만 문자열 s의 길이만으로도 충분히 basecondition을 작성할 수 있어 나중에 제거하였습니다.

String s같은 경우는 처음에 Stringbuilder를 활용하였지만 매번 초기화 되지않아 문제가 발생할 여지가 있고 다소 복잡해져 직관적인 String 타입으로 변환하였습니다. 시간이 타이트하여 최적화를 해야한다면 StringBuilder를 사용해야할 것 같습니다.