글 읽기 - 메모리 초과 개선안 추천받습니다

jojls1004 1년 전 0

다음과 같은 코드로 제출하면 메모리 초과가 뜨는데... 어떤 방안으로 이를 개선할 수 있을까요?

큐를 이용한 BFS방식입니다

import java.util.*;
import java.io.*;
public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int h = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken()),
				x = 0, y = 0, way = 0;
		int[][] map = new int[h][w];
		Queue<int[]> que = new LinkedList<>();
		que.add(new int[] {x, y});
		
		for(int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < w; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		
		while(!que.isEmpty()) {
			int[] save = que.poll();
			x = save[0]; y = save[1];
			
			if(x == w-1 && y == h-1) // 도착하면 +1
				way++;
			
			if(x > 0 && map[y][x-1] < map[y][x]) // 왼쪽 칸이 더 작으면 왼쪽 칸으로
				que.add(new int[] {x-1, y});
			
			if(x < w-1 && map[y][x+1] < map[y][x]) // 오른쪽 칸이 더 작으면 오른쪽 칸으로
				que.add(new int[] {x+1, y});
			
			if(y > 0 && map[y-1][x] < map[y][x]) // 위쪽 칸이 더 작으면 위쪽 칸으로
				que.add(new int[] {x, y-1});
			
			if(y < h-1 && map[y+1][x] < map[y][x]) // 아래쪽 칸이 더 작으면 아래쪽 칸으로
				que.add(new int[] {x, y+1});
		}
		
		bw.write(way + "");
		bw.close();
	}
}

djm03178 1년 전 0

방문 체크를 하지 않는 BFS는 지수 개의 정점을 큐에 넣게 될 수 있습니다.

jojls1004 1년 전 0

@djm03178 상하좌우 위치의 수가 현재 위치의 수보다 작을 때만 큐에 넣기 때문에 다시 되돌아갈 수 없는데 어떠한 연유로 방문 체크가 필요한가요?

djm03178 1년 전 0

이 코드는 모든 방문 경로를 전부 개별적으로 카운트하고 있습니다. 그러면 예를 들어, a->b, b->c, a->c의 간선이 있을 때, c는 큐에 총 몇 번 들어가게 될까요?

jojls1004 1년 전 0

아하 이 코드로 짜면 이미 지나갔던 칸을 다른 루트를 통해 지나가면서 무의미한 큐가 포함되는군요 애초에 최소 이동 횟수를 구하는 게 아니라 방법 수를 구하는 거니까 DFS가 더 짜기 쉬웠겠네요....

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

문제

문제

출처

ICPC

메모리 초과 개선안 추천받습니다

jojls1004 1년 전 0

djm03178 1년 전 0

jojls1004 1년 전 0

djm03178 1년 전 0

jojls1004 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말