글 읽기 - DFS + DP풀이 게시판 모든 반례 통과하는데, 틀리는 이유를 모르겠어요

jaeuk9407 3년 전 0

다익스트라인지 모르고 백트래킹으로 접근했습니다.

단순 구현으로는 시간초과가 있길래 DP를 도입해서 시간초과는 피했는데 통과를 못하네요.

(1,1)에서부터 DFS로 맵 내부를 탐색하는데, visited를 레퍼런스가 아닌 값으로 넘기면서 계속 탐색시켰습니다.

벽이 있는 1 자리면 부수고 가는 경우와 벽이 없는 0 자리면 그냥 가도록 했습니다.

재귀를 돌면서 현재 위치에서 이미 벽 부수는 행위를 기록하는 cnt가 더 작게 기록되어 있다면 더 진행하지 않도록 해서 불필요한 호출은 줄이도록 구현했구요.

다익스트라 풀이가 더욱 효율적이라는건 알겠는데, 이 백트래킹 풀이에서 구조적으로 잘못된 부분이 있을까요?

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

public class Main {
	static int miro[][];
	static boolean visited[][];
	static int ans;
	static int N, M;
	static int dx[] = {1, -1, 0, 0};
	static int dy[] = {0, 0, 1, -1};
	static int dp[][];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		miro = new int[N+1][M+1];
		visited = new boolean[N+1][M+1];
		dp = new int[N+1][M+1];
		
		for(int i = 1; i<= N; i++) {
			String line = br.readLine();
			for(int j = 1; j<=M; j++) {
				miro[i][j] = line.charAt(j-1) - '0';
			}
		}
		
		for(int i = 1; i<= N; i++) {
			for(int j = 1; j<=M; j++) {
				dp[i][j] = 101;
			}
		}
		
		ans = 101;
		dfs(1, 1, 0, visited);
		System.out.println(ans);
	}
	
	static void dfs(int row, int col, int cnt, boolean[][] visited) {
		if(row >= N && col>= M) {
			ans = Math.min(ans, cnt);
			return;
		}
		
		if(dp[row][col] <= cnt) {
			return;
		}
		
		visited[row][col] = true;
		dp[row][col] = cnt;
		
		for(int i = 0; i< 4; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			if(0 < nx && nx <= N && 0 < ny && ny <= M) {
				if(!visited[nx][ny]) {
					if(miro[nx][ny] == 1) {
						dfs(nx, ny, cnt+1, visited);
					}else {
						dfs(nx, ny, cnt, visited);
					}
				}
			}
		}
		visited[row][col] = false;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DFS + DP풀이 게시판 모든 반례 통과하는데, 틀리는 이유를 모르겠어요

jaeuk9407 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말