글 읽기 - 2178 시간초과 오류입니다.

hjemperor 6년 전 0

DFS로 했더니 시간초과 오류라고 떨어지는데, 혹시 제 소스에서 뭔가 수정이 필요한 부분이 있을까요??

import java.util.Scanner;



public class Main {
		
		static int N;
		static int M;
		static int [][]arr;
		static int min;
		
		static String[][]arr1;
		
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new int[N][M];
		
		min = N*M;		// 최소경로값 (모든경로로 가도 N by M 행렬이므로)
		
		for (int i=0; i<N; i++) {
			
			String string = sc.next();
			for (int j=0; j<M; j++) {
				arr[i][j] = string.charAt(j) - '0';
			}
		}
		
		DFS(0, 0, 1);
		
		System.out.println(min);
	}

	private static void DFS(int x, int y, int i) {
		
		// 도착지점에 도착했을 때
		if (x==N-1 && y==M-1) {
			if (min > i) {
				min = i;
			}
			return;
		}
		
		
		
		arr[x][y] = 0;		// 방문 표시 했음을 표시 0
		
		// 위쪽 이동 가능?
		if (x>0 && arr[x-1][y] != 0) {
			DFS(x-1, y, i+1);
		}
		
		// 아래쪽 이동 가능?
		if (x<N-1 && arr[x+1][y] != 0) {
			DFS(x+1, y, i+1);
		}
		
		// 왼쪽 이동 가능?
		if (y>0 && arr[x][y-1] != 0) {
			DFS(x, y-1, i+1);
		}
		
		// 오른쪽 이동 가능?
		if (y<M-1 && arr[x][y+1] != 0) {
			DFS(x, y+1, i+1);
		}
		
		arr[x][y] = 1;
	}
}

exqt 6년 전 1

dfs 로 탐색하시면 모든 가능한 경로에 대해 탐색하게 되는데

10 10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

이런 경우 경우의 수가 급격하게 증가합니다.

BFS를 쓰시는게 좋을 것 같네요

hjemperor 6년 전 0

결국 답은 BFS 일까요? 감사합니다!!

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

문제

문제

출처

ICPC

2178 시간초과 오류입니다.

hjemperor 6년 전 0

exqt 6년 전 1

hjemperor 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말