글 읽기 - [JAVA]16398번 자바 질문해요..

rkdwodms86 5년 전 0

왠만한 예제 테스트해봤는데 맞았는데 어디서 틀렸는지 모르겠습니다. 애초에 이렇게 풀면 안되는거였나요..

import java.util.Arrays;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		int C[][] = new int[N][N];

		int D[] = new int[N]; // 플로우 최소값

		int roop[][] = new int[N][2]; // 행성이 이어져있는지 확인하는 배열
		
		int rink[]=new int[N]; // 한 행성에 여러 행성이 연결되어있는걸 확인할때
		
		int temp=0;
		
		Arrays.fill(rink, -1);

		for (int i = 0; i < roop.length; i++) {
			roop[i][0] = -1;
			roop[i][1] = 0;
		}

		int minarray = 0; // i번의 행성과 연결된 행성를 찾는 변수

		int sum = 0; // 최소값 합

		for (int i = 0; i < D.length; i++) { // 최소값을 구하기 위해 최대값을 넣어줌

			D[i] = Integer.MAX_VALUE;

		}

		for (int i = 0; i < N; i++) { // 입력

			for (int j = 0; j < N; j++) {

				C[i][j] = in.nextInt();

			}

		}

		case1: for (int i = 0; (i < C.length)||!rink(roop); i++) {
			if(rink(roop)) {
				break;
			}
			
			if(i>=C.length) {
				for (int j = 0; j < rink.length; j++) {
					if(rink[j]==1) {
						temp=j;
						break;
					}
				}
				i=temp;
			}

			for (int j = 0; j < C.length; j++) {

				// i인 행과 j인 열에서 최소값을 구해서 최소값 배열을 넣되 0은 제외
				
				if (i == j) { // 배열의 원소가 0이면 패스
					continue;
				}

				if (roop[j][0] == i&&rink[i]==-1) { // (1,3)을 연결했으면 (3,1)은 연결할 필요 없으니 패스!!!!!!!!!!!!!!!!!!
					D[i] = Integer.MAX_VALUE;
					roop[i][0] = j;
					rink[i]=1; // 이 행성은 한번 연결되어있음을 알려줌
					

					continue case1; // continue case1;으로 할지 고민해보자

				}
				else if(roop[j][0] == i&&rink[i]==1) {
					
					continue;
				}


				if (D[i] > C[i][j]) { // 최소값 배열보다 작으면 배열에 넣는다

					D[i] = C[i][j];

					minarray = j;

				}

			}

			roop[i][0] = minarray;
			
			
			
		}


		for (int i = 0; i < D.length; i++) {

			if (D[i] != Integer.MAX_VALUE)

				sum = sum + D[i];

		}

		System.out.println(sum);

	}

	static boolean rink(int[][] roop) { // roop 배열이 서로 연결되는지 확인하는 중
		int[] test = new int[roop.length]; // 자바 값만 복사해야 될듯..
		double roopvalue=0;
		for (int i = 0; i < roop.length; i++) {
			test[i] = roop[i][1];
		}
		for (int i = 0; i < roop.length; i++) {
			if (roop[i][0] == -1) {
				continue;
			}
			else if(roop[roop[i][0]][0] == i) {
				roopvalue=roopvalue+0.5;
				if(roopvalue==1) {
					roop[roop[i][0]][1]=roop[roop[i][0]][1]+1;
				}
				continue;
			}
		
			roop[roop[i][0]][1] = roop[roop[i][0]][1] + + 1;

		}
		
		for (int i = 0; i < roop.length; i++) {
			if(roop[i][1]!=0&&roop[i][0]!=-1) {
				roopvalue=roop[i][1];
				roop[i][1]=0;
				roop[roop[i][0]][1]=roop[roop[i][0]][1]+(int)roopvalue;
				
			}
		}

		for (int i = 0; i < roop.length; i++) {
			if (roop[i][1] == roop.length - 1) {

				for (int j = 0; j < roop.length; j++) {
					roop[j][1] = test[j];
				}

				return true;
			}
		}

		for (int i = 0; i < roop.length; i++) {
			roop[i][1] = test[i];
		}
		return false;

	}

}

djm03178 5년 전 1

무슨 로직을 의도하신 건지 잘은 모르겠지만, 이 문제는 전형적인 MST (최소 스패닝 트리) 문제입니다. MST를 구하는 알고리즘으로는 유명한 것으로 크루스칼 알고리즘과 프림 알고리즘이 있으니 찾아 보시는 게 어떨까요?

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

문제

문제

출처

ICPC

[JAVA]16398번 자바 질문해요..

rkdwodms86 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말