[BaekJoon] 1103 게임 (Java)

1.  문제 링크

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

2.  문제

요약

• 형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 합니다.
• 일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓고, 그 다음에 다음과 같이 동전을 움직입니다.
  1. 동전이 있는 곳에 쓰여 있는 숫자 X를 봅니다.
  2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한 가지를 고릅니다.
  3. 동전을 위에서 고른 방향으로 X만큼 움직입니다. 이 때, 중간에 있는 구멍은 무시합니다.
• 만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료됩니다.
• 보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 50보다 작거나 같은 자연수인 보드의 세로 크기 N과 보드의 가로 크기 M이 주어지고 두 번째 줄부터 N개의 줄에 보드의 상태가 주어집니다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H입니다.
  • H는 구멍을 나타냅니다.
  • 가장 왼쪽 위칸은 H가 아닙니다.
• 출력: 첫 번째 줄에 문제의 정답을 출력합니다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M, answer;
    static boolean isInfinite;
    static char[][] map;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
    static boolean[][] visited;
    static int[][] count;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        map = new char[N][M]; // 보드의 상태
        count = new int[N][M]; // 각 위치까지 오는데 동전이 움직인 횟수
        visited = new boolean[N][M]; // 방문 체크 배열
        isInfinite = false; // 무한히 게임을 진행할 수 있는지 여부
        answer = 0; // 형택이가 동전을 움직일 수 있는 최대 횟수

        for(int row = 0; row < N; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < M; col++) {
                map[row][col] = info.charAt(col);
            }
        }
    }

    static void solution() {
        visited[0][0] = true;

        dfs(0, 0, 1);

        System.out.println(isInfinite ? -1 : answer);
    }

    static void dfs(int x, int y, int cnt) {
        if(cnt > answer)
            answer = cnt;

        count[x][y] = cnt;

        for(int dir = 0; dir < 4; dir++) {
            int cx = x + (dx[dir] * (map[x][y] - '0')), cy = y + (dy[dir] * (map[x][y] - '0'));

            if(isInMap(cx, cy) && map[cx][cy] != 'H') {
                if(visited[cx][cy]) {
                    isInfinite = true;
                    return;
                }

                if(count[cx][cy] > cnt)
                    continue;

                visited[cx][cy] = true;
                dfs(cx, cy, cnt + 1);
                visited[cx][cy] = false;
            }
        }
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < N && y >= 0 && y < M) return true;
        return false;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}

4  접근

• 보드의 가장 왼쪽 위에서부터 시작하므로 방문 체크 배열인 visited 배열의 가장 왼쪽 위 값을 true로 변경하여 방문 체크를 해줍니다.
• DFS를 통해 문제의 답을 구합니다.
  • count 배열의 현재 위치에서의 값을 현재까지 동전이 이동한 횟수로 갱신해줍니다.
  • 인접한 네 방향의 위치를 확인하여 동전의 이동을 진행합니다.
    • 인접한 위치가 보드 내에 존재하고 구멍이 아닐 때, 인접한 위치를 아직 방문하지 않았고 인접한 위치의 count 배열의 수가 현재까지 동전이 이동한 횟수보다 작거나 같다면 해당 위치의 방문 체크를 진행하고 재귀적으로 dfs 메서드를 호출하여 다음 위치들을 탐색합니다.
      • 인접한 위치가 보드 내에 존재하고 구멍이 아닐 때, 만약 인접한 위치가 이미 방문한 곳이라면 지금까지 이동한 경로로 계속 이동하며 무한히 게임을 진행할 수 있기 때문에 isInfinite 값을 true로 변경합니다.
  • 만약 현재까지의 동전 이동 횟수가 이전까지의 동전 이동 횟수보다 크다면 answer의 값을 갱신해줍니다.
• DFS를 마친 후에 isInfinite의 값을 확인하여 만약 true라면 무한히 게임을 진행할 수 있다는 뜻이므로 -1을, 그렇지 않다면 동전의 최대 이동 횟수인 answer를 출력합니다.