백준 1103 - 게임 (java)

문제 링크

접근

직사각형 보드 위 특정 지점에서 게임을 진행할 수 있는 최대 횟수(동전을 움직일 수 있는 횟수)는 변하지 않는다. 해당 횟수를 저장하면 연산 횟수를 크게 줄일 수 있다는 방향으로 접근.

풀이

시작점부터 갈 수 있는 4방향으로 dfs 탐색. return값을 통해서 갈 수 있는 경로를 하나씩 더함.
만약 범위 벗어나거나 구멍일때 - 1 리턴. 한 번 갈 수 있기 때문에
탐색하지 못한 부분일 때 - 다시 dfs를 돌리기. dfs 리턴값 + 1
탐색했던 부분일 때 - 해당 dp값 +1을 하기
현재 dfs 내에서 탐색중일때 - 싸이클

시행착오-> dfs탐색할때, 현재 dfs에서 탐색을 한 visited인지, 이전에 탐색했던 visited인지 구분을 해야함. 따라서, 현재 루트에서 방문한 곳은 -1로 초기화
반례)
4 3
133
5HH
HHH
21H

정답 코드(java/자바)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ1103 {
	static int n;
	static int m;
    //입력받은 보드, 해당 위치에서 갈 수 있는 횟수 저장할 배열
	static int[][] arr, dp;
    //무한루프 여부를 확인할 플래그
	static boolean flag = false;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		n = Integer.parseInt(str[0]);
		m = Integer.parseInt(str[1]);
		char c;
		arr = new int[n][m];
		dp = new int[n][m];
		
        //dp와 visited를 동시에 처리하기 위한 초기화
		for(int i = 0; i < n; i++) {
			for(int k = 0; k < m; k++) {
				dp[i][k] = -2;
			}
		}
		
        //빈칸은 -1로 입력
		for(int i = 0; i < n; i++) {
			str[0] = br.readLine();
			for(int k = 0; k < m; k++) {
				c = str[0].charAt(k);
				if(c == 'H') {
					arr[i][k] = -1;
				}
				else {
					arr[i][k] = (int)c - (int)'0';
				}
			}
		}
		System.out.println(dfs(0, 0));
	}

	private static int dfs(int idxI, int idxK) {
    	//현재 방문했다는 것을 알기 위해 -1로 초기화
		dp[idxI][idxK] = -1;
        //사방탐색을 위한 배열
		int[] di = {0, 0, 1, -1};
		int[] dk = {1, -1, 0, 0};
		int[] cnt = new int[4];
		int newI, newK;
        //사방탐색을 한 후, 갈 수 있는 횟수의 최댓값 찾기
		for(int i = 0; i < 4; i++) {
			newI = idxI + di[i]*arr[idxI][idxK];
			newK = idxK + dk[i]*arr[idxI][idxK];
            //범위를 벗어나거나 구멍일 때 : 1번
			if(newI<0||newK<0||newI>=n||newK>=m||arr[newI][newK] == -1) {
				cnt[i] = 1;
			}
			else {
            	//탐색한 적 없을 때 : dfs로 다시 탐색
				if(dp[newI][newK] == -2)
					cnt[i] = dfs(newI, newK) + 1;
                //해당 루트에서 탐색중일 때 : 싸이클
				else if(dp[newI][newK] == -1) {
					cnt[i] = -1;
					flag = true;
				}
                //탐색한 적 있을 때 : 이전값+1
				else {
					cnt[i] = dp[newI][newK]+1;
				}
			}
		}
		//무한루프일 때, return
		if(flag == true) {
			return -1;
		}
		
		//무한루프가 아닐 때 : 최댓값 찾은 후 return
		int max = Math.max(cnt[0], cnt[1]);
		max = Math.max(max, cnt[2]);
		max = Math.max(max, cnt[3]);
		dp[idxI][idxK] = max;
		return max;
	}

}