[백준] 1103번 게임 (JAVA)

문제

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

1103번: 게임

 

설명

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

처음 위치인 (0, 0)에서 시작하여 DFS을 진행한다. 나중에 사이클이 만들어지는지 확인하기 위한 visited 배열과 같은 좌표를 또 방문할 때 가지치기하기 위한 dp 배열을 만든다.

DFS를 진행하면서 현재 move와 maxMove를 비교하여 큰 값을 maxMove에 넣는다.

주어진 조건으로 상하좌우 이동하는데 이동할 구역이 구멍인지 이미 방문했던 곳인지 체크한다.

또한, 같은 좌표에 더 적은 move로 방문하면 가지치기로 방문하지 않는다.

static void dfs(int x, int y, int move) {
    // 1. 체크인
    visited[x][y] = true;
    dp[x][y] = move;

    // maxMove 최신화
    maxMove = Math.max(maxMove, move);

    // 2. 연결된 곳을 순회
    for (int i = 0; i < 4; i++) {
        int tx = x + MX[i] * (board[x][y] - '0');
        int ty = y + MY[i] * (board[x][y] - '0');

        // 3. 갈 수 있는가?
        if (tx >= 0 && tx < N && ty >= 0 && ty < M) {
            // 4. 목적지인가?
            if (board[tx][ty] == 'H')
                continue;
                
            // 방문했던 곳 재방문 -> 사이클 생성(동전을 무한번 움직일 수 있다)
            if (visited[tx][ty]) {
                cycleFlag = true;
                return;
            }

            // 같은 좌표에 더 적은 move로 방문하면 가지치기로 방문하지 않는다
            if (dp[tx][ty] > move)
                continue;

            // 5. 간다.
            dfs(tx, ty, move + 1);
        }
    }

    // 6. 체크아웃
    visited[x][y] = false;
}

 

전체 코드

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

public class Main {

    static final int[] MX = { -1, 1, 0, 0 };
    static final int[] MY = { 0, 0, -1, 1 };

    static int N, M;
    static char[][] board;
    static int[][] dp;
    static boolean[][] visited;
    static boolean cycleFlag;
    static int maxMove;

    static void dfs(int x, int y, int move) {
        // 1. 체크인
        visited[x][y] = true;
        dp[x][y] = move;

        // maxMove 최신화
        maxMove = Math.max(maxMove, move);

        // 2. 연결된 곳을 순회
        for (int i = 0; i < 4; i++) {
            int tx = x + MX[i] * (board[x][y] - '0');
            int ty = y + MY[i] * (board[x][y] - '0');

            // 3. 갈 수 있는가?
            if (tx >= 0 && tx < N && ty >= 0 && ty < M) {
                // 4. 목적지인가?
                if (board[tx][ty] == 'H')
                    continue;

                // 방문했던 곳 재방문 -> 사이클 생성(동전을 무한번 움직일 수 있다)
                if (visited[tx][ty]) {
                    cycleFlag = true;
                    return;
                }

                // 같은 좌표에 더 적은 move로 방문하면 가지치기로 방문하지 않는다
                if (dp[tx][ty] > move)
                    continue;

                // 5. 간다.
                dfs(tx, ty, move + 1);
            }
        }

        // 6. 체크아웃
        visited[x][y] = false;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new char[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++) {
                board[i][j] = str.charAt(j);
            }
        }

        cycleFlag = false;
        maxMove = 0;

        dfs(0, 0, 1);

        if (cycleFlag)
            System.out.println("-1");
        else
            System.out.println(maxMove);
    }
}