글 읽기 - 맞았는데, 이전 코드의 시간 초과 이유가 궁금합니다. (자바 백트래킹)

jkh9615 3년 전 0

안녕하세요. 문제를 맞긴 했는데, 시간초과 코드와 비교했을 때 알고리즘적으로 변경된건 없습니다.

단지 visit배열의 초기화? 부분이 달라졌는데요, 이것이 어떻게 시간초과까지 영향을 미치는지 궁금합니다.

전체 코드를 올리기에는 지저분해 보일 것 같아, main함수 및 DFS함수를 올리겠습니다!

제가 의심이 가는곳은 17번 라인에 new 키워드로 초기화해주는 부분밖에 없다고 생각하는데,

해당 부분이 시간초과를 불러일으킬 만큼 무거운 부분인가요??

+아차, 0%도 못가고 시작하자마자 시간초과가 나왔습니다 ㅋㅋ!....

//시간 초과 코드
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n][m];
		
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				visit = new boolean[n][m];
				DFS(i, j, map[i][j], 0);
				max = Math.max(max, get_except(i, j));
			}
		}
		System.out.println(max);
	}
	public static void DFS(int x, int y, int tmp, int level) {
		visit[x][y] = true;
		if(level == 3) {
			max = Math.max(max, tmp);
		}else {
			for(int i = 0; i < 4; i++) {
				int new_x = x + dir[i][0];
				int new_y = y + dir[i][1];
				if(new_x >= 0 && new_y >= 0 && new_x < n && new_y < m) {
					//범위 안에 있으면
					if(!visit[new_x][new_y]) {
						visit[new_x][new_y] = true;
						DFS(new_x, new_y, tmp+map[new_x][new_y], level+1);
						visit[new_x][new_y] = false;
					}
				}
			}
		}
	}


//AC 코드
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n][m];
		visit = new boolean[n][m];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				visit[i][j] = true;
				DFS(i, j, map[i][j], 0);
				visit[i][j] = false;
				max = Math.max(max, get_except(i, j));
			}
		}
		System.out.println(max);
	}
	public static void DFS(int x, int y, int tmp, int level) {
		if(level == 3) {
			max = Math.max(max, tmp);
			return;
		}else {
			for(int i = 0; i < 4; i++) {
				int new_x = x + dir[i][0];
				int new_y = y + dir[i][1];
				if(new_x >= 0 && new_y >= 0 && new_x < n && new_y < m) {
					//범위 안에 있으면
					if(!visit[new_x][new_y]) {
						visit[new_x][new_y] = true;
						DFS(new_x, new_y, tmp+map[new_x][new_y], level+1);
						visit[new_x][new_y] = false;
					}
				}
			}
		}
	}

slah007 3년 전 1

new boolean[n][m]은 n*m의 메모리 할당하고 0으로 초기화하기 때문에 O(nm)이 걸릴 것 같습니다.

그냥 visit[i][j] = 0은 이보다 n*m배 빠릅니다.

jkh9615 3년 전 0

감사합니다. 시간초과 나는 코드에서

new boolean 으로 초기화하는것을 clearVisit()함수를 제작하여 visit배열의 모든 값을 false로 초기화하니까

시간초과 문제는 해결됐습니다.

그러나, 바뀐 코드 : 2930ms, 위 AC코드 : 1060ms인 점을 확인했을 때 매번 visit배열을 초기화하는 것이 아니라, AC코드처럼 필요한 부분만 초기화 해야겠음을 배우고갑니다.

감사합니다!

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

문제

문제

출처

ICPC

맞았는데, 이전 코드의 시간 초과 이유가 궁금합니다. (자바 백트래킹)

jkh9615 3년 전 0

slah007 3년 전 1

jkh9615 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말