글 읽기 - 정답이나 풀이좀.

teahyuk 8년 전 0

문제 풀이같은거 해주실 수 있나요? 개인 IDE를 사용해서 테스트케이스 바꿔가면서 보면 정답인것 같은데, 계속 오답이 나네요. 메모리사이즈문제거나, 시간문젠가 해서 봐도, 큰 문제 없는 것 같구요..

import java.util.Scanner;

public class Main{
	static int[][] adjustedMatrix;
    public static void main(String args[]){
    	long start = System.nanoTime();	//사용시간 계산용. 제출시주석.
        Scanner sc = new Scanner(System.in);
        int n,m;
        n=sc.nextInt();
        m=sc.nextInt();
        adjustedMatrix = new int[n+1][n+1];
        int[][] answer = new int[n+1][n+1];
        int MAX = Integer.MAX_VALUE-1000; //integer over flow 방지
        for (int i = 0; i < adjustedMatrix.length; i++) {
			adjustedMatrix[0][i] = i;
			adjustedMatrix[i][0] = i;
			answer[0][i] = i;
			answer[i][0] = i;
		}
        for (int i = 1; i < adjustedMatrix.length; i++) {
			for (int j = 1; j < adjustedMatrix.length; j++) {
				adjustedMatrix[i][j] = MAX;
			}
			adjustedMatrix[i][i] = 0;
		}
        for(int i = 0; i<m; i++){
        	int x = sc.nextInt();
        	int y = sc.nextInt();
        	adjustedMatrix[x][y] = adjustedMatrix[y][x] = sc.nextInt();
        }
        sc.close();
        
        //출력..
        for (int i = 0; i < adjustedMatrix.length; i++) {
			for (int j = 0; j < adjustedMatrix.length; j++) {
				System.out.print(adjustedMatrix[i][j]+" ");
			}
			System.out.println();
		}
        
        //dijkstra전용 변수배열 미리 선언,
        boolean[] visited = new boolean[adjustedMatrix.length];
        Direction[] answerI = new Direction[adjustedMatrix.length];
        for (int i = 0; i < answerI.length; i++) {
			answerI[i] = new Direction(0,0);
		}
        for (int s = 1; s < adjustedMatrix.length; s++) {
			//dijkstra 시작.
        	for (int i = 1; i < adjustedMatrix[s].length; i++) {	//초기화.
				answerI[i].direction = i;
				answerI[i].distance = adjustedMatrix[s][i];
				visited[i] = false;
			}
        	visited[s] = true;
   
        	for (int i = 2; i < adjustedMatrix.length; i++) { //첫번째는 세팅 해놓았으니 2번째부터
        		int min = MAX,minIdx=0;
				for (int j = 1; j < answerI.length; j++) {
					if(answerI[j].distance < min && visited[j] != true){
						minIdx = j;
						min = answerI[j].distance;
					}
				}
				visited[minIdx] = true;
				
				for (int j = 1; j < adjustedMatrix[minIdx].length; j++) {
					int newDist = adjustedMatrix[minIdx][j] + answerI[minIdx].distance;
					if(newDist<answerI[j].distance){
						answerI[j].distance = newDist;
						answerI[j].direction = answerI[minIdx].direction;
					}
				}
        	}
        	//출력..
			for (int j = 1; j < answerI.length; j++) {
        		answer[s][j] = answerI[j].direction;
        		if(s!=j)
					System.out.print(answer[s][j]);
				else
					System.out.print("-");
        		if(j!=answerI.length-1)
        			System.out.print(" ");
        	}
			System.out.println();
		}
        
        ////////알고리즘 구현 시간, 및 사용 메모리계산.(제출시 주석.)///////
        long end = System.nanoTime();
		double time = (end-start)/1000000.0;
		System.out.println("end processing Time : "+time+"(ms)");
		long free  = Runtime.getRuntime().freeMemory();
	    long total = Runtime.getRuntime().totalMemory();
	    long max   = Runtime.getRuntime().maxMemory();
	    System.out.format("Total Memory : %6.2f MB%n", (double) total / (1024 * 1024));
	    System.out.format("Free  Memory : %6.2f MB%n", (double) free  / (1024 * 1024));
	    System.out.format("Max   Memory : %6.2f MB%n", (double) max   / (1024 * 1024));

    }
}
class Direction{
	int direction;
	int distance;
	Direction(int _dir, int _dis){
		this.direction = _dir;
		this.distance = _dis;
	}
}

baekjoon 8년 전 1

정답이 여러 개가 나올 수 있는 문제네요.

채점을 수정해야 겠습니다.

baekjoon 8년 전 1

재채점했습니다. https://www.acmicpc.net/rejudge/status/233

baekjoon 8년 전 1

70번줄은

answerI[j].direction = minIdx; 이 되어야 맞을거 같은데

고쳐도 틀리네요. ㅠㅠ

teahyuk 8년 전 0

그 문제 자체에서 최소 경로 찾았을 때에 제일 처음 방문해야 되는 노드를 정리하는 행렬을 구해야 하는 걸로 알고 있습니다. 그러려면 저런식으로 구조체를 따로 하나 만들어서 이전구조체를 계속 불러오는 식으로 해야 하기때문에 answer[j].direction을 만든거구요, 이전 구조체의 direction을 불러오게 만들었습니다.

만약 말씀해주신대로 고친다면 아마 바로 직전 노드를 계속 업데이트하기때문에 최소경로 찾았을 때에 마지막으로 방문해야하는 노드를 출력하게 될 것입니다.

아무튼 dijkstra 공부는 제대로 했네요., ㅎㅎ 한번 더 확인 부탁드려요~.

baekjoon 8년 전 1

아 그러게요 제가 잠시 오해를 했네요.

지금 틀리는 경우가 뭔지를 보면, 출력하는 배열에 사이클이 있습니다.

a -> c로 갈 때 b를 거쳐야한다고 출력하는데

a -> b로 갈 때는 c를 거쳐야한다고 출력하는 경우가 있습니다.

teahyuk 8년 전 0

오옷 감사합니다 확인해보고 수정 해보겠습니다~^^

teahyuk 8년 전 0

저 죄송하지만 오류나는 케이스를 못찾겠어서그런데.. 오류나는 케이스 입력값좀 알려주실 수 있나요??.....

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

문제

문제

출처

ICPC

정답이나 풀이좀.

teahyuk 8년 전 0

baekjoon 8년 전 1

baekjoon 8년 전 1

baekjoon 8년 전 1

teahyuk 8년 전 0

baekjoon 8년 전 1

teahyuk 8년 전 0

teahyuk 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말