글 읽기 - 출력초과가 나오는데 원인을 잘 모르겠어서요 조언 부탁드립니다.

woodyu995 6년 전 0

소스코드는 다음과 같습니다.

간단한 설명은 주석으로 달아 놓았습니다.

제가 처음 생각했을때는 minHeapify과정에서 무한 루프에 빠진다고 생각해서

그부분을 주석으로 처리하고 제출을 해보았는데 그래도 출력초과가 나오더라고요

혹시나 해서 출력쪽을 주석 처리하여 제출 해보았는데 이때는 출력초과가 아닌 틀렸다고 나와서요

(제가 체점 시스템을 잘 몰라서 그렇습니다만... 만약 minHeapify가 무한 루프에 빠진다면 그부분을 주석처리했을때 틀렸습니다라고 출력이 되야하는거 아닌가요?)

이걸로 봐서는 결과를 출력하는 쪽에서 뭐가 문제가 있는것 같은데요 아무리봐도 출력쪽에는 문제가 없어보여서요ㅠㅠ 조언부탁드립니다.

참고로 예제 케이스는 정상 작동합니다.

감사합니다.

package DijkstraAlgorithm_1753;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
/*
 *  Node클래스를 선언한다
 *  클래스에는 nodeNumber와 node와 연결된 node를 가르키는 리스트가 저장되어있다.
 *  시작 노드는 Node클스를 통해 객체를 생성할때 번호와 d값만 지정되며 weight는 0이다
 *  목적지에 해당하는 노드는 number와 weight가 지정되고 d값은 0이다
 *  만약 2 -> 3 (weight가 5인경우) node배열에는 number가 2고 weight가 0 그리고 d 가 무한대(만약 시작 노드라면 0)인 객체가 저장되고
 *  number가 2인 객체의 adjustList에는 weight를 5로 갖고 d값이 0이며 number가 3인 node객체가 저장된다
 *  노드의number값으로  해당 노드에 접근하기위해 hashMap을 이용한다.
 *  node리스트를 대상으로 priority heap 정렬을할 때 노드의 number와 배열의 index는 서로 달라지기 때문이다.
 *  
 */


public class Main {
	class Node {
		int number;
		int weight;
		int d;
		ArrayList<Node> adjustList;

		public Node(int number) {
			this.number = number;
			this.weight = 0;
			adjustList = new ArrayList<>();
			d = Integer.MAX_VALUE;
		}

		public Node(int number, int weight) {
			// TODO Auto-generated constructor stub
			this.number = number;
			this.weight = weight;
			adjustList = new ArrayList<>();

		}

		public void addNode(Node add) {
			adjustList.add(add);
		}

		public ArrayList<Node> getList() {
			return this.adjustList;
		}

	}

	public static void main(String[] args) {

		Main test = new Main();
		Scanner sc = new Scanner(System.in);
		int row = sc.nextInt();
		int edge = sc.nextInt();
		int start = sc.nextInt() - 1;
		Node[] vertex = new Node[row];

		test.init(vertex, edge, sc, start);
		HashMap<Integer, Node> result = test.solve(vertex, vertex.length, start);
		
		for (int i = 0; i < row; i++) {
			Node temp = result.get(i);
			if (temp.d == Integer.MAX_VALUE) {
				System.out.println("INF");
			} else {
				System.out.println(temp.d);
			}
		}

	}

	public void swap(Node[] node, int target, int source) {
		Node temp = node[target];
		node[target] = node[source];
		node[source] = temp;
	}


	public void buildHeap(Node[] node, int lenght) {
		int root = lenght / 2 - 1;

		while (root >= 0) {
			minHeapify(node, root, lenght);
			root--;
		}
	}

	public void minHeapify(Node[] node, int root, int length) {
		int left = root + 1;
		int right = left + 1;
		int min = 0;
		if (left < length && right < length) {
			min = node[left].d > node[right].d ? right : left;

		}else if (left < length && node[left] != null) {
			min = left;
		}else{
			return;
		}
		if(node[min].d < node[root].d){
			Node temp = node[min];
			node[min] = node[root];
			node[root] = temp;
			minHeapify(node, min, length);
		}
	}

	public HashMap<Integer, Node> solve(Node[] node, int length, int start) {
		HashMap<Integer, Node> hashMap = new HashMap<>();
		for (int i = 0; i < node.length; i++) {
			hashMap.put(i, node[i]);
		}
		buildHeap(node, length);
		while (length > 0) {
			for (Node n : hashMap.get(node[0].number).getList()) {
				if (n.number != start) {
					if (hashMap.get(n.number).d > hashMap.get(node[0].number).d
							+ n.weight) {
						Node temp = hashMap.get(n.number);
						temp.d = hashMap.get(node[0].number).d + n.weight;
						hashMap.put(n.number, temp);
					}
				}
			}

			swap(node, 0, length - 1);
			length--;
			minHeapify(node, 0, length);
		}
		return hashMap;
	}

	public void init(Node[] node, int n, Scanner sc, int start) {
		for (int i = 0; i < node.length; i++) {
			node[i] = new Node(i);
			if (i == start) {
				node[i].d = 0;
			}
		}
		for (int i = 0; i < n; i++) {
			int s = sc.nextInt() - 1;
			int e = sc.nextInt() - 1;
			int weight = sc.nextInt();

			node[s].addNode(new Node(e, weight));

		}
	}

}

answn8376 6년 전 0

Integer.MAX_VALUE 이게 값이 너무 커서 그런게 아닐까요

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

문제

문제

출처

ICPC

출력초과가 나오는데 원인을 잘 모르겠어서요 조언 부탁드립니다.

woodyu995 6년 전 0

answn8376 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말