뒤죽박죽 코딩 이야기

2021년 7월 15일 목요일 - 비가 오고 천둥이 와르르 쾅쾅

오늘 올려볼 문제는 1103번 게임이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

문제만 봐서는 감이 잘 안잡힐 것이다.
왜냐하면 내가 그랬으니깐...

하지만 입력 예제들을 보는 순간 감이 딱 잡힐 것이다!!

자 이제 좀 보드게임의 느낌이 난다!

1. 각 보드에는 구멍이 있거나 숫자 하나가 적혀있다.
2. 게임은 좌표 (1, 1) 에서 시작하며 동전이 있는 보드에서 상, 하, 좌, 우 한 방향으로 이동할 수 있다.
3. 이동할 때에는 보드에 적힌 숫자만큼 직진하여야 한다.
4. 직진하여 보드게임 판의 크기를 넘어가게 되거나, 보드 위에 있는 구멍에 빠지게 되면 게임은 끝이 난다.
5. 이 때 보드게임을 가장 오래동안 즐기고 싶을 때 최대 몇 번 움직일 수 있는지 구하는 것이 이 문제이다!

풀이 및 코드

문제를 보자마자 생각이 든 것은 바로 DFS 기법이었다!

DFS 기법을 사용하면서 구멍에 대한 예외와 범위에 대한 예외만 처리해주고 방문했던 곳을 또 방문하는 경우 무한으로 게임을 진행하는 것이 가능하기에 -1을 리턴하여 따로 처리만 해주면 될 줄 알았으나...

시간초과가 나버렸다...

DFS 특성상 방문했던 곳으로 되돌아와 다른 곳을 방문하는 방식이기 때문에 판의 크기가 커지면 커질 수록 시간 복잡도는 O(방문해야하는 개수 ^ n) 으로 늘어나기 때문에 이에 대한 처리를 해주어야 한다.

그래서 생각한게 DP이다!

DFS를 통해서 탐색을 하다가 해당 좌표에 가장 최대 횟수를 저장하는 방식을 사용하면서
현재 탐색중인 횟수가 해당 좌표에 횟수보다 작을 경우 탐색을 하지 않는 방향으로 코드를 짜서 시간을 단축시켰다.

풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

    // arr은 보드게임 판, dp는 회수 저장 배열, v는 방문 여부 배열
    // result는 결과

    static int[][] arr, dp;
    static boolean[][] v;

    static int result = 0, row, col;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input_nums = br.readLine().split(" ");

        row = Integer.parseInt(input_nums[0]);
        col = Integer.parseInt(input_nums[1]);

        // 사실 2씩 크게 동적할당 할 필요는 없지만 해주었다..
        arr = new int[row + 2][col + 2];
        v = new boolean[row + 2][col + 2];
        dp = new int[row + 2][col + 2];

        for(int i = 0; i < row + 2; i++)
        {
            Arrays.fill(v[i], true);
        }


        // 입력받는 코드 구멍이 입력으로 들어올 경우 -1을 arr에 저장했다.
        for(int i = 1; i <= row; i++)
        {
            String[] input = br.readLine().split("");

            for(int j = 0; j < input.length; j++)
            {
                if(input[j].equals("H"))
                    arr[i][j + 1] = -1;
                else
                    arr[i][j + 1] = Integer.parseInt(input[j]);

                v[i][j + 1] = false;
            }
        }

        solve(1, 1, 0);

        bw.write(result + "\n");
        bw.flush();

    }

    // dfs, dp 기법을 사용한 함수
    // x, y는 좌표, length는 현재 이동 횟수를 말한다.
    public static int solve(int x, int y, int length)
    {
        // 해당 좌표의 적혀있는 숫자를 go에 저장한다.
        int go = arr[y][x];

        // 해당 좌표가 구멍이라면
        // result보다 현재 이동 횟수가 더 큰지 살펴보고 result를 업데이트한다.
        if(go == -1)
        {
            if(result < length)
                result = length;

            return 0;
        }

        // 또한 해당 좌표의 이전 이동 횟수가 이번에 탐색하려는 이동 횟수보다 작다면
        // result보다 현재 이동 횟수가 더 큰지 살펴보고 result를 업데이트한다.
        if(dp[y][x] < length)
            dp[y][x] = length;

        // 이번 탐색에서 해당 좌표는 방문한 것으로 표시.
        v[y][x] = true;

        // 범위 체크 (아래와 같은 형식의 코드가 4번 반복됨)
        // 범위를 벗어난다면
        // result보다 현재 이동 횟수가 더 큰지 살펴보고 result를 업데이트한다.
        if(x + go > col)
        {
            if(result < length + 1)
                result = length + 1;
        }
        else
        {
            // 탐색하려고 하는 좌표가 방문했다면
            // result를 -1로 만들고 -1을 리턴한다.
            if(v[y][x + go])
            {
                result = -1;
                return -1;
            }
            else
                // 탐색하려는 좌표의 이전 이동 횟수보다 이번에 탐색하려는 이동 횟수보다 작다면
                if(dp[y][x + go] < length + 1)
                    // 재귀를 통해서 탐색하려는 좌표를 탐색한다. 이 때 return 값이 -1이라면 -1을 리턴한다.
                    if(solve(x + go, y, length + 1) == -1)
                        return -1;

        }

        if(x - go < 1)
        {
            if(result < length + 1)
                result = length + 1;
        }
        else
        {
            if(v[y][x - go])
            {
                result = -1;
                return -1;
            }
            else
                if(dp[y][x - go] < length + 1)
                    if(solve(x - go, y, length + 1) == -1)
                        return -1;
        }

        if(y + go > row)
        {
            if(result < length + 1)
                result = length + 1;
        }
        else
        {
            if(v[y + go][x])
            {
                result = -1;
                return -1;
            }
            else
                if(dp[y + go][x] < length + 1)
                    if(solve(x, y + go, length + 1) == -1)
                        return -1;
        }

        if(y - go < 1)
        {
            if(result < length + 1)
                result = length + 1;
        }
        else
        {
            if(v[y - go][x])
            {
                result = -1;
                return -1;
            }
            else
                if(dp[y - go][x] < length + 1)
                    if(solve(x, y - go, length + 1) == -1)
                        return -1;
        }

        v[y][x] = false;

        return 0;
    }

}

제출 화면

처음 시간복잡도 생각을 못한 것 빼면은 내 논리가 괜찮았던 나름 뿌듯한 문제였다.

오늘 처음으로 블로그에 제대로된 글을 적어보는데 이 글이 누군가에게 도움이 됐으면 좋겠다!