[백준 1103] 게임- 자바(solved.ac - 골드 2)

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

1103번: 게임

풀이

문제를 보았을 때 알 수 있는 힌트

문제를 가볍게 생각하고 푼다면 dfs로 풀면 되겠다는 생각을 하게 된다. 하지만 여기서 함정은 다시 돌아 올수있다는 점과 다른곳에서 돌아와 위치를 더 빠르게 오는 경우도 있다. 이를 해결하기 위해서 DP를 활용하면 시간초과를 해결할 수 있다.

 

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

public class Main {
	// baekjoon 1103 게임
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[] nx = new int[] { -1, 1, 0, 0 };
	static int[] ny = new int[] { 0, 0, -1, 1 };
	static int answer = -1;
	static int r;
	static int c;
	static Character[][] graph;
	static boolean[][] visited;
	static int[][] dp;
	static boolean flag;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		// 첫 위치

		// 그래프 만들기
		graph = new Character[r][c];
		visited = new boolean[r][c];
		dp = new int[r][c];

//		// 첫 위치는 방문 한걸로 처리
		visited[0][0] = true;

		for (int i = 0; i < r; i++) {
			String temp = br.readLine();
			for (int j = 0; j < c; j++) {
				graph[i][j] = temp.charAt(j);
			}
		}
		dfs(0, 0, 1);
		if(flag) System.out.println(-1);
		else System.out.println(answer);

	}

	public static void dfs(int y, int x, int count) {
		if (count > answer)
			answer = count;
		dp[x][y] = count;
		int mut = Integer.parseInt(graph[x][y].toString());

		for (int k = 0; k < 4; k++) {
			int dx = x + nx[k] * mut;
			int dy = y + ny[k] * mut;
			if (!(0 <= dx && dx < r && 0 <= dy && dy < c && graph[dx][dy] != 'H')) {
				continue;
			}
			if(visited[dx][dy]) {
				flag=true;
				return;
			}
			if(dp[dx][dy]>count) continue;
			visited[dx][dy] = true;
			dfs(dy,dx,count+1);
			visited[dx][dy] = false;
			

		}
	}

}

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/java/baekjoon1103/Main.java

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리