[JAVA] 백준 1103번 게임

[HAVE TO DO]

STUDYING : JAVA

---

문제링크 : https://www.acmicpc.net/problem/1103

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

public class Main {
	
	// 무한으로 움직일 수 있다면 -1 출력
	
	static int[] mx = {-1, 1, 0, 0}; //x축 조이스틱
	static int[] my = {0, 0, -1, 1}; //y축 조이스틱
	
	static int N, M; //N : 세로크기, M : 가로크기 (<=50)
	static int[][] dp; // 동전이 기록하며 가는 길
	static boolean[][] visited;
	static char[][] map;
	static int max = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		dp = new int[N][M];
		map = new char[N][M];
		visited = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			String e = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = e.charAt(j);
			}
		}

        dfs(0, 0);
		System.out.println(max);
		
	}
	
	static void dfs(int x, int y) {
		// 한 번 방문했던 점을 방문했다면 무한하게 움직일 수 있는 것
		if(visited[x][y]) {
			System.out.println(-1);
			System.exit(0);
		}
		visited[x][y] = true;
		// 갈 수 있는 곳을 순회 for(좌, 우, 위, 아래)
		for (int i = 0; i < 4; i++) {
			// - '0'을 하면 char이 int로 바뀜
			int tx = x + (map[x][y] - '0')*mx[i];
			int ty = y + (map[x][y] - '0')*my[i];
			if(inside(tx, ty) && map[tx][ty] != 'H') {
				dp[tx][ty] = dp[x][y] + 1;
				max = Math.max(max, dp[tx][ty] + 1);
				dfs(tx, ty);
			}
			
		}		
		visited[x][y] = false;
	}
	
	// 동전이 보드판 안에 있는가?
	static boolean inside(int x, int y) {
		if(0 <= x && x < N && 0 <= y && y < M) return true;
		else return false;
	}

}

시간 초과가 미친듯이 떴던 문제.. dp 가지치기를 제대로 못해서 최장 루트가 있음에도 그 루트 계속 살펴봐서 발생했던 것 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	// 무한으로 움직일 수 있다면 -1 출력
	
	static int[] mx = {-1, 1, 0, 0}; //x축 조이스틱
	static int[] my = {0, 0, -1, 1}; //y축 조이스틱
	
	static int N, M; //N : 세로크기, M : 가로크기 (<=50)
	static int[][] dp; // 동전이 기록하며 가는 길
	static boolean[][] visited;
	static char[][] map;
	static int max = 0;
	static int count = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		dp = new int[N][M];
		map = new char[N][M];
		visited = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			String e = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = e.charAt(j);
			}
		}
		
		dfs(0, 0);
		
		bw.write(String.valueOf(max));
		
		br.close();
		bw.flush();
		bw.close();
		
	}
	
	static void dfs(int x, int y) {
		visited[x][y] = true;
		count++;
		
		if(count > max) {
			max = count;
		}
		
		dp[x][y] = count;
		for (int i = 0; i < 4; i++) {
			// - '0'을 하면 char이 int로 바뀜
			int tx = x + (map[x][y] - '0')*mx[i];
			int ty = y + (map[x][y] - '0')*my[i];
			
			if(0 > tx || tx >= N || 0 > ty || ty >= M || map[tx][ty] == 'H') continue;
			
			if(visited[tx][ty]) {
				System.out.println(-1);
				System.exit(0);
			}
			
			if(dp[tx][ty] > count) continue;
			dfs(tx, ty);			

		}
		
		visited[x][y] = false;
		count--;
	}

}

포인트는 if(dp[tx][ty] > count) continue; 이거였다.

이미 tx, ty의 위치에서 갈 수 있는 최장 루트가 존재하기에 dfs를 돌 필요가 없다.