[백준2178] 미로탐색 - 자바(JAVA)

1. 문제

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

2178번: 미로 탐색

 

2. 풀이

DFS 알고리즘을 사용해서 문제를 풀었다.

2차원 배열 min에 해당 칸에 몇 번만에 도착할 수 있는지 `최소값`을 저장하도록 했다.

다음 (next_r, next_c)에 몇 칸만에 왔는지(depth+1)를  min[next_r][next_c]과 비교해서 최솟값이 아닐 시에 탐색을 중단하도록 해서 탐색시간을 줄였다.

처음에 depth+1과 min[next_r][next_c]가 같을 때에도 탐색하도록 했다가 시간초과가 나서 depth+1이 작을 때만 탐색하도록 했더니 패스가 되었다 !!

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static int N, M;
	static int[][] map;
	static int[] dr = { -1, 0, 1, 0 }; // 상, 우, 하, 좌
	static int[] dc = { 0, 1, 0, -1 };
	static int[][] min;
	static int result;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input = br.readLine().split(" ");

		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);

		map = new int[N][M];
		min = new int[N][M];

		for (int i = 0; i < N; i++) {
			String tmp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = tmp.charAt(j) - '0';
			}
		}

		result = Integer.MAX_VALUE;
		min[0][0] = 1;
		dfs(1, 0, 0);

		System.out.println(result);

	}

	public static void dfs(int depth, int R, int C) {
		if (R == N - 1 && C == M - 1) {
			result = Math.min(result, depth);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int next_r = R + dr[i];
			int next_c = C + dc[i];

			if (next_r < 0 || next_r >= N || next_c < 0 || next_c >= M)
				continue;

			if (map[next_r][next_c] == 0)
				continue;
			
			if (min[next_r][next_c] == 0) {
				min[next_r][next_c] = depth + 1;
				dfs(depth + 1, next_r, next_c);
			} else if (min[next_r][next_c] < depth + 1) {
				continue;
			} else if (min[next_r][next_c] > depth + 1) {
				min[next_r][next_c] = depth + 1;
				dfs(depth + 1, next_r, next_c);
			}

		}

	}

}