글 읽기 - [메모리초과][JAVA] 2146 도와주세요

dlcksdnd321 4년 전 0

bfs를 이용해서 섬의 번호를 체크하고

bfs를 이용해서 섬부터 가까운 섬까지 거리를 체크했습니다.

일정 거리가 계산되면 그것보다 높으면 bfs를 멈추도록 했고

큐에 추가될때 방문을 표시해 중복을 막았습니다.

그런데도 메모리초과가 발생하는데 왜그런지 알려주실분 계신가요 ㅠㅠ??

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static boolean[][] visit;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int result = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1)
					map[i][j] = -1;
			}
		}
		visit = new boolean[N][N];
		int cnt = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == -1) {
					Queue<loc> q = new LinkedList();
					q.add(new loc(i, j));
					map[i][j] = cnt;
					while (!q.isEmpty()) {
						loc nowl = q.poll();
						for (int k = 0; k < 4; k++) {
							int nextr = nowl.r + dr[k];
							int nextc = nowl.c + dc[k];
							if (nextr >= 0 && nextr < N && nextc >= 0 && nextc < N && !visit[nextr][nextc]
									&& map[nextr][nextc] != 0) {
								q.add(new loc(nextr, nextc));
								visit[nowl.r][nowl.c] = true;
								map[nextr][nextc] = cnt;
							}
						}
					}
					cnt++;
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) {
					int[][] visit = new int[N][N];
					for (int k = 0; k < N; k++) {
						visit[k] = Arrays.copyOf(map[k], N);
					}
					Queue<loc> q = new LinkedList();
					q.add(new loc(i, j));
					int distance = 0;
					int nowisland = map[i][j];
					while (!q.isEmpty()) {
						if (result <= distance)
							break;
						int qsize = q.size();
						for (int index = 0; index < qsize; index++) {
							loc now = q.poll();
							for (int k = 0; k < 4; k++) {
								int nextr = now.r + dr[k];
								int nextc = now.c + dc[k];
								if (nextr >= 0 && nextr < N && nextc >= 0 && nextc < N) {
									if (visit[nextr][nextc] != nowisland && visit[nextr][nextc] > 0) {
										result = result > distance ? distance : result;
										q.clear();
										index = qsize;
										break;
									} else if (visit[nextr][nextc] == 0) {
										q.add(new loc(nextr, nextc));
										visit[nextr][nextc] = -1;
									}
								}
							}
						} // 한칸의 거리까지 추가
						distance++;
					}

				}
			}
		}
		System.out.println(result);

	}
}

class loc {
	int r, c;

	loc(int x, int y) {
		r = x;
		c = y;
	}
}

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

문제

문제

출처

ICPC

[메모리초과][JAVA] 2146 도와주세요

dlcksdnd321 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말