[BOJ] 백준 1103 - 게임 풀이

1. 문제

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

1103번: 게임

2. 풀이

• 단순 DFS로 문제 해결 시 시간초과 발생
• 풀이 Point는 DFS + DP로 DP를 이용하여 다음에 탐색하려는 위치의 DP 값이 지금 현재 Depth보다 크다면 그 부분으로는 탐색을 하지 않는 것이다.
• 그리고 동전을 무한번 움직일 수 있다는 것은 사이클이 발생할 수 있다는 것이므로 4방 탐색을 체크하면서 방문했던 지점을 또 방문할 수 있다면 이는 사이클이 발생할 수 있다는 것이다. 이때는 flag를 true로 하여 -1을 출력하게 한다.
• 주요 자료구조
  • boolean[][] visited : 방문을 체크하는 배열
  • int[][] dp : 이 위치에 도달했을 때의 depth값을 저장할 dp 배열
  • boolean isLoop : 무한 루프가 발생했는지 판단하는 flag
    
    
• 주요 로직 포인트
  • gameDFS 함수를 타고 들어왔다면, dp배열의 그 위치에 depth를 저장한다. -> 이는 이 위치까지 최대로 이 depth까지 왔다는 것을 의미한다. 
  • map 배열의 값만큼 떨어져있는 곳의 4방 탐색을 진행할 때, 방문한 지점이 있다면, 사이클이 발생할 수 있다는 것이므로 isLoop flag를 true로 만든다.
  • 다음에 탐색하려는 위치의 DP 값이 지금 Depth보다 크다면 그 쪽으로는 갈 이유가 없으므로, 현재 Depth가 다음 위치의 DP 값보다 크거나 같을 때만 진행한다. 
    
    
    
    

3. 소스코드

package dfs;

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

public class Game {
    static boolean[][] visited;
    static char[][] map;

    static int N, M;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int[][] dp;
    static int result = Integer.MIN_VALUE;
    static boolean isLoop = false; // 무한 루프 플래그

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

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

        // map 초기화
        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        // visited, dp 배열 초기화
        visited = new boolean[N][M];
        dp = new int[N][M];

        // DFS : x, y, depth
        visited[0][0] = true;
        gameDFS(0, 0, 1);

        // isLoop 플래그가 true라면 -1 출력
        if (isLoop) {
            bw.write("-1");
        } else {
            bw.write(Integer.toString(result));
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // dfs 함수
    private static void gameDFS(int x, int y, int depth) {
        dp[x][y] = depth;
        result = Integer.max(depth, result);

        // 내 위치의 값 확인
        int val = map[x][y] - '0';

        // 상하좌우로 이동시켜 주기
        for (int i = 0; i < 4; i++) {
            int xf = x + (dx[i] * val);
            int yf = y + (dy[i] * val);

            if (isAvailable(xf, yf) && map[xf][yf] != 'H') {

                // 만약 방문을 햇다면 사이클이 발생했으므로
                if (visited[xf][yf]) {
                    isLoop = true;
                    return;
                }

                // 다음에 탐색하려는 위치의 DP 값이 지금 Depth보다 크면 재귀를 탈 이유가 없다.
                if (depth >= dp[xf][yf]) {
                    // 방문 처리
                    visited[xf][yf] = true;

                    gameDFS(xf, yf, depth + 1);

                    // 다시 돌아와서는 visited 초기화
                    visited[xf][yf] = false;
                }
            }
        }
    }

    // 범위를 넘는지 판단하는 함수
    private static boolean isAvailable(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}

4. 배운점

• DP + DFS 경우는 모든 경로를 탐색하는 것이 아닌 DP 값에 따라 재귀를 타는 경우를 가지치기 한다는 것을 기억!!
  
  

5. 점수

• 60 / 100