[백준 1103] 게임

문제 출처

사용 언어: Java

1. 구상

• 현재 위치에서 상하좌우로 움직였을 때의 숫자를 확인하여 그 중 가장 작은 숫자를 택하기
  

• 무한으로 움직이는지 확인하기 위해 방문 여부 기록 (visited 배열)
  → 무한으로 움직인다면 게임을 그 자리에서 종료시키고 -1 출력

• DP 알고리즘을 이용하여 최대 경우의 수를 구하기

• 구멍에 빠지거나 보드판을 벗어나면 바로 종료

알고리즘 및 코드 참고 링크

2. 구현

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

public  class Main {	
	static int max, n, m;
	//동전을 무한으로 움직이는지
	static boolean isCycle = false;
	//중간중간 값을 저장하는 dp배열
	static int[][] dp; 
	//보드판 배열
	static char[][] map;
	//방문여부 저장하는 배열
	static boolean[][] visited;
	//상하좌우로 이동
	static int[] moveX = {0, 0, -1, 1};
	static int[] moveY = {-1, 1, 0, 0};
	
	
	public static void main(String[] args) throws NoSuchElementException, IOException {
		Scanner s = new Scanner(System.in);		
		
		//세로
		n = s.nextInt();
		//가로
		m = s.nextInt();
		
		dp = new int[n][m];
		map = new char[n][m];
		visited = new boolean[n][m];
		
		//보드판 입력받기
		for (int i = 0; i < n; i++) {			
				map[i] = s.next().toCharArray();
		}
		
		//가장 왼쪽에서 시작하므로 방문을 기록
		visited[0][0] = true;
		
		dfs(0, 0, 1);
		
		//동전이 무한대로 움직인다면 -1 출력
		if(isCycle) {
			System.out.println("-1");
		}
		//그렇지 않다면 움직인 최대 횟수 출력
		else {
			System.out.println(max);
		}
	}
	
	//dfs 알고리즘 (i, j) 위치에서 시작, 이동 횟수를 저장하는 moveCount
	static void dfs (int x, int y, int moveCount) {
		//(i, j) 위치의 X값 구하기
		int moveSquare = Character.getNumericValue(map[y][x]);
		dp[y][x] = moveCount;
		
		if (moveCount > max)
			max = moveCount;
		
		for (int i = 0; i < moveX.length; i++) {
			int nextX = x + (moveSquare * moveX[i]);
			int nextY = y + (moveSquare * moveY[i]);
			
			//다음 위치가 보드판을 벗어나면 종료
			if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) 
				continue;
			
			//구멍에 빠지면 종료
			if(map[nextY][nextX] == 'H')
				continue;
			
			//이동횟수가 그 전 기록보다 크면 종료
			if (moveCount < dp[nextY][nextX])
				continue;
			
			//사이클이라면 종료
			if (visited[nextY][nextX]) {
				isCycle = true;
				return;
			}
			
			//다음 위치 방문 표시
			visited[nextY][nextX] = true;
			//다음 위치에서 dfs 실행 (재귀호출)
			dfs(nextX, nextY, moveCount + 1);
			//
			visited[nextY][nextX] = false;
			
			
		}
			
		
	}

}