[JAVA] 백준 1103번: 게임

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

1103번: 게임

✅ 골드 Ⅱ

 

🔶 풀이

보드에 적힌 숫자만큼 동,서,남,북 4방향으로 이동하면서 최대 몇 번의 동전을 움직일 수 있는지 구하는 문제.

dfs와 dp를 이용하는 문제.

 

1️⃣ 동전이 구멍에 빠지거나 보드의 바깥으로 나가면 게임 종료

2️⃣ 동전을 무한번 움직일 수 있을 경우 -1을 출력

 

게임이 종료되는 조건은 위와 같다.

1️⃣번 조건은 dfs, bfs를 한 번이라도 풀어봤다면 쉽게 해결할 수 있다.

if (nx < 0 || ny < 0 || nx > M-1 || ny > N-1) continue;

 

2️⃣번 조건은 방문여부를 따져주면 해결할 수 있다.

if (visited[nx][ny]) {
    isCheck = true;
    return;
}

 

 

<최종코드>

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

public class Main {
    static char[][] map;
    static int[][] dp;
    static int ans;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int N, M;
    static boolean[][] visited;
    static boolean isCyle = 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());
		
        map = new char[N][M];
        visited = new boolean[N][M];
        dp = new int[N][M];
		
        for (int i=0; i<N; i++) {
            map[i] = br.readLine().toCharArray();
        }
		
        visited[0][0] = true;
        dfs(0, 0, 1);
		
        if (isCyle) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
	
    public static void dfs (int x, int y, int cnt) {
        int move = Character.getNumericValue(map[y][x]);
        dp[y][x] = cnt;
		
        if (cnt > ans) {
            ans = cnt;
        }
		
        for (int d=0; d<4; d++) {
            int nx = x + (move * dx[d]);
            int ny = y + (move * dy[d]);
			
            // 범위를 벗어나거나 구멍에 빠졌을 경우
            if (nx < 0 || ny < 0 || nx > M-1 || ny > N-1 || map[ny][nx] == 'H') continue;
            
            // 이미 더 큰 값이 존재할 경우
            if (dp[ny][nx] > cnt) continue;
            
            // 동전이 무한번 반복할 경우
            if (visited[ny][nx]) {
                isCyle = true;
                return;
            }
			
            // 백트래킹
            visited[ny][nx] = true;
            dfs(nx, ny, cnt+1);
            visited[ny][nx] = false;
        }
    }
}