백준 1103번: 게임

문제 설명

• https://www.acmicpc.net/problem/1103
• 보드의 숫자만큼 상,하,좌,우 원하는 곳으로 움직일 수 있습니다.
  최대한 많이 이동하면 몇번 이동할 수 있는지 구해야 합니다.
  H위에 멈추면 더이상 이동하지 않습니다.
  무한으로 이동할 수 있다면 -1을 출력합니다.

접근법

틀린 이유

• BFS로 접근했습니다.

  • 이 문제는 BFS로 사이클을 찾기 어렵습니다.
  • H를 만나면 바로 return을 했습니다. BFS에서는 같은 hierarchy에 H말고 가능한 경우의 수가 존재할 수 있기 때문에 return하면 안됩니다. (DFS는 H를 방문하지 않거나 H에서 바로 멈추면 됩니다.)
    ----
    2HH
    HHH
    111
    ----
    (0,0)에서 오른쪽으로 가면 H지만 return하지 않고 다음 경우의 수인 아래로 가서 추가 진행을 해야 합니다.

• 사이클을 찾는 방법을 몰랐습니다.

  • DFS의 경우 방문배열을 백트래킹처럼 지속적으로 리셋시켜 줍니다. 만약 방문한 곳을 다시 방문했다면 사이클이 됩니다.

dp

이 문제는 방문한 칸을 계속 방문할 수 있기 때문에 boolean의 visit배열보다 dp로 확인하는 게 좋습니다.
똑같은 (x,y)로 방문하더라도 더 높은 횟수로 방문하는 게 이득입니다. 그렇기 때문에 갈 수 있지만 더 낮은 곳은 방문하지 않습니다.

if(dp[nx][ny] < dp[x][y]+1){
	dp[nx][ny] = dp[x][y] +1;
}

정답

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

public class Main {
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	static int maxVal = Integer.MIN_VALUE;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		char[][] board = new char[N][M];
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}
		int[] now = {0,0};
		boolean[][] v = new boolean[N][M];
		v[0][0] = true;
		int[][] dp = new int[N][M];
		int cnt = 1;
		if(DFS(N,M,now, board, v, cnt, dp)) {
			System.out.println(-1);
		}else {			
			System.out.println(maxVal);
		}
	}

	public static boolean DFS(int N, int M, int[] now, char[][] board, boolean[][] v, int cnt, int[][] dp) {
		maxVal = Math.max(maxVal,  cnt);
		int multiple = board[now[0]][now[1]] -'0';
		for (int d = 0; d < 4; d++) {
			int nx = now[0] + dx[d]*multiple;
			int ny = now[1] + dy[d]*multiple;
			if(0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] != 'H'
					&& dp[nx][ny] < dp[now[0]][now[1]]+1) {
				if(v[nx][ny]) return true; // 사이클 발견
				dp[nx][ny] = dp[now[0]][now[1]] +1; // 더 높은 값으로 업데이트
				v[nx][ny] = true; // 방문표시
				if(DFS(N,M,new int[] {nx,ny},board,v,cnt+1,dp)) return true;
				v[nx][ny] = false; // 방문배열 초기화
			}
		}
		return false;
	}	
}