[Java][백준 1103][dfs + dp] 게임

문제

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

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

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

입력

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

 

---

🌈 풀이 후기

• 처음에 dfs로 접근하려다가 N과 M이 최대 50이라 dp를 함께 적용하였습니다.
• dfs에 dp를 적용하는 문제가 종종 나오는데 아직 익숙하지 않아서 몇문제 더 풀어볼 예정입니다.
• dp를 통한 가지치기가 핵심입니다.

👩‍🏫 문제 풀이

1. (0,0)부터 시작해서 dfs를 확인한다.

2. 만약 방문했던 곳이라면 무한루프가 되기에 종료시키고 -1을 출력한다.

3. 만약 지금 방문하려는 곳이 현재 cnt 값보다 크다면 굳이 방문하지 않는다. (어차피 반복되는데 최대 움직임 횟수를 구해야 하기 때문)

4. dfs를 돌면서 cnt 최고값을 계속 갱신해준다. 

 

 

package com.Boj.Day12;

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

// dfs + dp
public class BOJ_G2_1103_게임 {
	static int N, M;
	static char[][] map;
	static int[][] dp;
	static int cnt = 0;
	static int max = 0;
	static boolean[][] visit;
	static boolean isInfinite;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	private static void dfs(int r, int c, int cnt) {
		if (cnt > max)
			max = cnt;
		dp[r][c] = cnt;

		for (int i = 0; i < 4; i++) {

			int nr = r + dr[i] * (map[r][c] - '0');
			int nc = c + dc[i] * (map[r][c] - '0');

			if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] != 'H') {
				// 무한루프 체크
				if (visit[nr][nc]) {
					isInfinite = true;
					return;
				}
				
				// 가지치기. 방문하려는 곳이 현재 count보다 크면 굳이 방문하지 않는다?? 
				if (dp[nr][nc] > cnt)
					continue;

				visit[nr][nc] = true;
				dfs(nr, nc, cnt + 1);
				visit[nr][nc] = false;

			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		map = new char[N][M];
		dp = new int[N][M];
		visit = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String tmp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = tmp.charAt(j);
			}
		}

		isInfinite = false;
		visit[0][0] = true;
		dfs(0, 0, 1);

		if (isInfinite)
			System.out.println(-1);
		else
			System.out.println(max);
	}

}