글 읽기 - 메모리 초과 봐주십시오.. (JAVA, BFS)

ssifood 5년 전 0

왜 메모리 초과일까요? 이클립스로는 되거든요;;

보통 다른분들은 cnt 이런걸로 계산했는데

저는 그냥 length[][] 란 이차원배열로 총 거리를 다 할당했어요.

그래서 메모리 초과인가요??

같이 검토해봐주시면 감사하겠습니다. 행님들

import java.util.*;

public class Main {

	public static void main(String[] args) {
		int n, m;
		Point st, now;
		int ad[][], length[][];
		boolean visit[][];
		char ch[];
		Queue<Point> q;

		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		ad = new int[n + 1][m + 1];
		length = new int[n + 1][m + 1];
		visit = new boolean[n + 1][m + 1];
		q = new LinkedList<Point>();
		st = new Point(1, 1);
		now = new Point(1, 1);

		for (int i = 1; i <= n; i++) {
			ch = new char[n];
			ch = sc.next().toCharArray();
			for (int j = 1; j <= m; j++) {
				visit[i][j] = false;
				if (ch[j - 1] == '1')
					ad[i][j] = 1;
				    
				else
					ad[i][j] = 0;
			}
		}

		q.offer(st);
		length[st.x][st.y] = 1;
		while (!q.isEmpty()) {

			int sz = q.size();
	
			for (int z = 0; z < sz; z++) {

				// cnt++; 그냥 cnt로 카운트 하면 모든 큐를 다센다. 중복포함
				now = q.poll();

				if (now.x == n && now.y == m) {
					System.out.println(length[now.x][now.y]);
					System.exit(0);
					break;
				}
					

				// 따로 조건을 줄꺼면, 조건범위도 따로 주어야 배열 범위 넘는 오류안나네!!! 20161015 이중방

				if (now.x > 1 && !visit[now.x - 1][now.y] && ad[now.x - 1][now.y] == 1) {
					length[now.x - 1][now.y] = length[now.x][now.y] + 1;
					visit[now.x][now.y] = true;
					q.offer(new Point(now.x - 1, now.y));
				}
				if (now.x < n && !visit[now.x + 1][now.y] && ad[now.x + 1][now.y] == 1) {
					length[now.x + 1][now.y] = length[now.x][now.y] + 1;
					visit[now.x][now.y] = true;
					q.offer(new Point(now.x + 1, now.y));
				}
				if (now.y > 1 && !visit[now.x][now.y - 1] && ad[now.x][now.y - 1] == 1) {
					length[now.x][now.y - 1] = length[now.x][now.y] + 1;
					visit[now.x][now.y] = true;
					q.offer(new Point(now.x, now.y - 1));
				}
				if (now.y < m && !visit[now.x][now.y + 1] && ad[now.x][now.y + 1] == 1) {
					length[now.x][now.y + 1] = length[now.x][now.y] + 1;
					visit[now.x][now.y] = true;
					q.offer(new Point(now.x, now.y + 1));
				}
			}

		} // while
	
	}// main

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}// MAin

djm03178 5년 전 0

visit에 true를 넣을 때 [now.x][now.y]에 하는 것이 아니고 다음 방문하려는 장소에 해야 합니다.

djm03178 5년 전 0

그리고 채점 서버에서 프로그램에 넣는 입력을 이클립스에서 똑같이 넣어보신 것도 아니고, 그 때 최대 메모리 사용량이 얼마인지 확인해보신 것도 아닌데 어떻게 이클립스에서는 된다고 확신하셨는지 궁금합니다.

ssifood 5년 전 0

채점 서버에서 주는 모든 경우에 대한 메모리초과까지는 파악하지못하였고, 단지 예제에 주어진 값들만 이클립스에서 돌려봤는데 성공했다는..

매우 주관적인 것입니다;;;

djm03178 5년 전 0

그렇기 때문에 "~에서 된다"는 말은 의미가 없습니다. 알고리즘 문제의 목표는 "조건 내의 어떤 입력에 대해서도 제한 안에 올바른 답을 출력할 수 있게 하는 것"이기 때문에, 몇 개의 예제에 대해서 잘 되는 것을 확인했다고 해서 "이 코드는 대략 맞는 코드일 것이다"라고 생각해서는 안 됩니다.

sjmsjm1111 5년 전 0

대부분의 백준문제는 히든케이스가 있습니다. 예제만 통과하면 안되세요~

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

문제

문제

출처

ICPC

메모리 초과 봐주십시오.. (JAVA, BFS)

ssifood 5년 전 0

djm03178 5년 전 0

djm03178 5년 전 0

ssifood 5년 전 0

djm03178 5년 전 0

sjmsjm1111 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말