[백준/Java] 1103 : 게임

백준 1103번 '게임' 풀이입니다. 동전의 최대 이동 횟수를 구하되, 무한 루프 가능 여부도 판별해야 합니다. DFS 탐색에 메모이제이션(DP)을 결합하고, 현재 경로에서 재방문 시 사이클로 판단해 -1을 반환했습니다. 단순 DFS로는 시간 초과가 났고, DP를 적용해 이미 계산한 위치를 재사용해 O(N×M)에 해결했습니다.

---

📌 문제 정보

• 번호: 1103
• 제목: 게임
• 난이도: Gold 2
• 분류: DFS, 그래프 탐색, 다이나믹 프로그래밍(DP), 사이클 판별

---

💡 접근 방식

DFS 기반 탐색에 DP(메모이제이션)를 결합하여 해결했습니다. 무한히 움직일 수 있는 경우를 판별하기 위해 사이클 감지를 함께 구현했습니다.

---

🔹 단계별 풀이

1단계 – 사이클 판별: DFS 중 현재 경로에서 재방문 시 즉시 -1 반환

2단계 – DP 적용: 이미 계산한 위치의 최대 이동 횟수 저장, 중복 탐색 방지

3단계 – 결과: 각 방향에서 얻은 최대값 + 1 반환

---

💻 핵심 코드

static int dfs(int r, int c) {
    if (visited[r][c]) return -1;
    if (dp[r][c] != 0) return dp[r][c];

    visited[r][c] = true;
    int max = 0;

    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i] * map[r][c];
        int nc = c + dc[i] * map[r][c];

        if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] != 0) {
            int res = dfs(nr, nc);
            if (res == -1) return -1;
            max = Math.max(max, res);
        }
    }

    visited[r][c] = false;
    dp[r][c] = max + 1;
    return max + 1;
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N × M)
• 공간 복잡도: O(N × M)

---

📄 전체 코드

package B1103;

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

public class Main {
    static int N, M;
    static int[][] map;
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};
    static boolean[][] visited;
    static int[][] dp;

    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());
        map = new int[N][M];
        visited = new boolean[N][M];
        dp = new int[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);
                map[i][j] = c == 'H' ? 0 : c - '0';
            }
        }
        System.out.println(dfs(0, 0));
    }

    static int dfs(int r, int c) {
        if (visited[r][c]) return -1;
        if (dp[r][c] != 0) return dp[r][c];
        visited[r][c] = true;
        int max = 0;
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i] * map[r][c];
            int nc = c + dc[i] * map[r][c];
            if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] != 0) {
                int res = dfs(nr, nc);
                if (res == -1) return -1;
                max = Math.max(max, res);
            }
        }
        visited[r][c] = false;
        dp[r][c] = max + 1;
        return max + 1;
    }
}