[백준] 1103 게임 java

문제

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

입력

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

 

풀이

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

public class Main {
    static final int[] dx = {1, -1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};
    static BufferedReader br;
    static StringTokenizer st;
    static int n, m, max;
    static int[][] board, dp;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        init();
        dfs(0, 0, 0);
        System.out.println(max);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        max = Integer.MIN_VALUE;
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        board = new int[n][m];
        dp = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                char c = str.charAt(j);
                if(c == 'H') {
                    board[i][j] = 0;
                } else {
                    board[i][j] = c - '0';
                }
            }
        }
    }

    static void dfs(int x, int y, int cnt) {
        //싸이클이 생겼다면 바로 탈출
        if(visited[x][y]) {
            max = -1;
            return;
        }
        //이미 전에 지나온 적 있는 곳
        if(dp[x][y] > 0) {
            //현재 이동횟수보다 크거나 같은 경우 가볼 필요 x
            if(dp[x][y] >= cnt) {
                return;
            }
        }
        //아직 지나가지 않았거나 현재 이동횟수가 더 큰 경우 dp값 갱신하고 계속 탐색
        dp[x][y] = cnt;

        //체크인
        visited[x][y] = true;

        //연결된 곳을 순회 : 상, 하, 좌, 우
        for(int i = 0; i < 4; i++) {
            int xx = dx[i] * board[x][y] + x;
            int yy = dy[i] * board[x][y] + y;

            //갈 수 있는가? : 보드판을 벗어나지 않으면서 구멍에도 빠지지 않는 곳
            if(xx >= 0 && yy >= 0 && xx < n && yy < m && board[xx][yy] > 0) {
                //간다.
                dfs(xx, yy, cnt+1);
            }
            // 물에 빠지거나 구멍에 빠지게 된다면
            else {
                //사이클이 이미 돌았을 경우 그냥 리턴
                if(max == -1){
                    visited[x][y] = false;
                    return;
                }
                //물에 빠진 횟수까지 해서 max값 갱신
                max = Math.max(max, cnt+1);
            }
        }
        //체크 아웃
        visited[x][y] = false;
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

알고리즘 에서의 주석의 중요성에 대해서 깨달았다 ! 주석으로 수도코드같이 먼저 글로 작성하고 코드를 작성해야 로직이 꼬이지 않고 척척 구현이 잘됐다.

 

이 문제는 dp + dfs 문제이다.

 

dp의 점화식은 dp[x][y] = max(상, 하, 좌, 우에서 각각 왔을 때 이동 횟수) 이다. TIL이 나지 않게 하려면 지금 이동 횟수보다 이미 지나온 위치가 더 횟수가 많을 경우 가볼 필요는 없다. 그러니 가지치기를 잘해주어야 한다.

 

나머지는 상, 하, 좌, 우 별로 물에 빠지거나 구멍에 빠지면 이동 횟수를 현재 최대값과 비교해 갱신해주었다. 

 

그리고 아직 갈 길이 있다면 계속 나아가다가 이미 방문한 위치를 재방문 했을 경우엔 사이클이 돌기 때문에 -1을 출력해주도록 하면 된다.