글 읽기 - 자바) 시간초과 나요.

bfryn1004 6년 전 0

시간초과가 나는데, 혹시 어떤 부분에서 그런 지 알려주시면 감사하겠습니다 ㅠ

import java.util.Scanner;

public class Main {
	static int min = 1000001;
	static int n, m;
	static String str;
	static char maze[][] = new char[100][100];
	final static char blockedWay = '0';
	final static char pathWay = '1';
	final static char visitedWay = '2';
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		for (int i = 0; i < n; i++){
			maze[i] = sc.next().toCharArray();
		}
		sc.close();
		solve(0, 0, 1);
		System.out.println(min);
	}
	
	public static void solve(int x, int y, int cnt){
		if (!(0 <= x && x < n) || !(0 <= y && y < m)
				|| maze[x][y] == blockedWay
				|| maze[x][y] == visitedWay)
			return;
		
		if (cnt > min) return;
		else if (x == n - 1 && y == m - 1) {
			if (min > cnt) min = cnt;
			return;
		}
		else{
			maze[x][y] = visitedWay;
			solve(x + 1, y, cnt + 1);
			solve(x - 1, y, cnt + 1);
			solve(x, y + 1, cnt + 1);
			solve(x, y - 1, cnt + 1);
			maze[x][y] = pathWay;		// 방문 경로를 원상복구
			return;
		}
	}
}

djm03178 6년 전 1

최단거리를 DFS로 풀면 시간복잡도가 엄청나게 커집니다. 경로는 아주 많을 수 있기 때문입니다. 최단거리 문제는 BFS로 풀어야 됩니다.

bfryn1004 6년 전 0

감사합니다~ BFS라는 것도 공부해봐야 겠네요 ㅎㅎ

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

문제

문제

출처

ICPC

자바) 시간초과 나요.

bfryn1004 6년 전 0

djm03178 6년 전 1

bfryn1004 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말