[백준BOJ] 1103번 게임.java

 

백준 저지에서 게임을 자바를 통해 풀어 보았다. 

 

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

1103번: 게임

 

1103번 게임.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1103번 게임

문제

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

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

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

설명

dfs와 dp를 통해 풀 수 있다.

 

dfs를 통해 보드 위를 검색하되 해당 위치까지 이동 수를 dp배열을 통해 저장한다. 만약 현재 dp에 저장된 이동 수보다 작다면 해당 방문을 종료한다.

코드

//1103번 게임.java
package boj20211216;

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

public class 게임_1103 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int answer=0;
    static boolean check=false;
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		String[][] board = new String[N][M];
		
		for(int i=0;i<N;i++) {
			String line = br.readLine();
			for(int j=0;j<M;j++) {
				board[i][j] = line.substring(j,j+1);
			}
		}
		
		int[][] visit = new int[N][M];
		int[][] dp = new int[N][M];
		visit[0][0]=1;
		dfs(0, 0, visit, N, M, board,dp);
		
		if(check)System.out.println(-1);
		else System.out.println(answer-1);
	}
    
    static void dfs(int i, int j, int[][] visit, int N, int M, String[][] board, int[][] dp) {
    	int[] di= {0,0,1,-1};
    	int[] dj = {1,-1,0,0};
    	dp[i][j]=visit[i][j];
    	for(int d=0;d<4;d++) {
    		int n = Integer.parseInt(board[i][j]);
    		int nextI = i+di[d]*n;
    		int nextJ = j+dj[d]*n;
    		
    		if(answer<visit[i][j]+1) {
				answer = visit[i][j]+1;
			}
    		
    		if(0<=nextI&&nextI<N&&0<=nextJ&&nextJ<M) {
    			if(board[nextI][nextJ].equals("H")) {
    				if(answer<visit[i][j]+1) {
    					answer = visit[i][j]+1;
    				}
    			}
    			else if(visit[nextI][nextJ]==0) {
    				if(dp[nextI][nextJ]>visit[i][j])continue;
    				visit[nextI][nextJ] = visit[i][j]+1;
    				dfs(nextI, nextJ, visit, N, M, board,dp);
    				visit[nextI][nextJ] = 0;
    			}
    			else{
    				check=true;
    				return;
    			}
    		}
    		else if(answer<visit[i][j]+1) {
    			answer = visit[i][j]+1;
    		}
    	}
    }
}