글 읽기 - 메모리 초과 질문입니다ㅠ

bangseung 5년 전 0

메모리 초과

말 그대로 프로그램이 문제에 적혀있는 메모리 제한보다 많은 메모리를 사용했을 때 발생합니다.
C/C++과 같은 경우에는 함수를 호출 할 때, 함수 내에서 수정하지 않는 변수를 call-by-value로 호출했는지 확인해보세요.

공지사항에 이렇게 나와있는데, 저는 java로 문제풀이를 하긴 했지만 어디가 문제인가요??

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	static int N, K, time;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		
		BFS(N);
	}
	
	public static void BFS(int x) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(x);
		
		Outter : while(!queue.isEmpty()) {
			int size = queue.size();
			
			for(int i=0; i<size; i++) {
				int current = queue.poll();
				
				if(current == K) {
					System.out.println(time);
					break Outter;
				} else {
					if(current-1>=0) queue.offer(current-1);
					if(current+1<=100000) queue.offer(current+1);
					if(current*2<=100000) queue.offer(current*2);
				}
			}
			time++;
		}
	}
}

djm03178 5년 전 1

모든 BFS는 반드시 방문 체크를 해야 합니다.

djm03178 5년 전 1

그러지 않으면 큐에 중복된 원소가 여럿 들어가고, 그것이 반복되다보면 시간/공간복잡도가 모두 지수가 되기 때문에 메모리가 감당할 수 없습니다. 설령 메모리를 무한으로 준다고 하더라도 시간이 감당할 수 없습니다.

bangseung 5년 전 1

visited 체크해주니까 해결 되었어요 정말 감사합니다!!

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

문제

문제

출처

ICPC

메모리 초과 질문입니다ㅠ

bangseung 5년 전 0

메모리 초과

djm03178 5년 전 1

djm03178 5년 전 1

bangseung 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말