글 읽기 - [자바] 메모리 초과 - 클래스 하나 더 생성한게 문제일까요

corya4 4년 전 0

방문한 노드 저장시킬때 인스턴스로 받으려고 한게 문제일까요?

메모리쪽 공부가 부족한 걸까요 ㅠㅠ

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

class Memoria{
	private int x;
	private int y;
	
	Memoria(int i, int j){
		x = i;
		y = j;
	}
	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + x;
		result = prime * result + y;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Memoria other = (Memoria) obj;
		if (x != other.x)
			return false;
		if (y != other.y)
			return false;
		return true;
	}
}


public class Salesman_circuit {
	static int[][] cities;
	static int[] point;
	static ArrayList<Memoria> memoria = new ArrayList<Memoria>();
	static int min = 0;
	private static int circuit;
	public static void main(String[] args) throws IOException {
		setting();
		start();
		System.out.println(min);
	}
			
	static void setting() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		circuit = Integer.parseInt(br.readLine());
		if(!(2<=circuit && circuit <= 16)) {
			System.exit(0);
		}
		StringTokenizer stn;
		int i = 0;
		int j = 0;
		while(true) {
			stn = new StringTokenizer(br.readLine(), " ");
			if(cities == null) {
				cities = new int[stn.countTokens()][stn.countTokens()];
			}
			while(stn.hasMoreTokens()) {
				cities[i][j] = Integer.parseInt(stn.nextToken());
				j++;
			}
			i++;
			j = 0;
			if(i > cities.length-1) {
				break;
			}
		}
	}
	static void start() {
		for(int i = 0; i < cities.length; i++) {
			for(int j = 0; j <cities[i].length; j++) {
				if(i != j) {
					point = new int[]{i,j};
					DFS(i,j,0,0);
					memoria.clear();
				}
			}
		}
	}
	static void DFS(int i, int j, int roop, int sum) {
		System.out.println(sum);
		if(roop == circuit ) { 
			if(i == point[0] && j == point[1]) {
				if(min == 0) {
					min = sum;
				}else if(min > sum) {
					min = sum;
				}
			}
			return;
		}else if(roop > circuit) {
			return;
		}
		
		Deque<Memoria> load = new LinkedList<Memoria>();
		
		if(i > 0) {
			load.push(new Memoria(i-1,j));
		}
		if(j > 0) {
			load.push(new Memoria(i,j-1));
		}
		if(i < cities.length-1) {
			load.push(new Memoria(i+1,j));
		}
		if(j < cities[i].length-1) {
			load.push(new Memoria(i,j+1));
		}
		while(!load.isEmpty()) {
			int xi = load.peek().getX();
			int xj = load.peek().getY();
			if(xi != xj && (cities[xi][xj] != 0)  && !memoria.contains(load.peek())) {
				memoria.add(load.poll());
				DFS(xi, xj, roop+1, sum+cities[i][j]);
				memoria.remove(memoria.size()-1);
			}else {
				load.poll();
			}
		}
	}
}

pichulia 4년 전 1

75~77번째 줄은 무엇을 의도한거죠?

예제의 입력을 그대로 따라보자면 cities는 크기가 [0][10]짜리 배열이 되는건데.. 절대 이걸 의도했을 것 같지는 않습니다.

그리고 문제를 푸는 로직이 아주 기묘합니다. 왜 인접한 도시로만 이동하시는거죠? 이 로직은 문제에서 요구하는 알고리즘과 상이합니다. 다시 생각해보세요.

corya4 4년 전 0

감사합니다! 인접한 도시로만 이동해야 할게 아니였군요 !

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

문제

문제

출처

ICPC

[자바] 메모리 초과 - 클래스 하나 더 생성한게 문제일까요

corya4 4년 전 0

pichulia 4년 전 1

corya4 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말