글 읽기 - 완전탐색을 이용해서 풀었습니다. 반례나 코드 문제점 찾아주세요.

rhdtha01 4년 전 0

외판원 순회 2 문제를 완전탐색을 이용해서 풀었습니다.

순열을 이용하면 될 것 같아서 첫번째 줄에서 받은 숫자 n 만큼의 길이를 배열로 두고 그 배열에 0~n-1까지를 삽입합니다.

해당 배열을 순열로 돌리면서 그 순서대로 방문하게 됩니다.

여기에서 0을 만나면 그 순열은 쓰지 않고 다음 순열로 넘어가는 코드입니다.

해당 예제에 대한 답은 잘 나옵니다.

어느 부분에서 "틀린다"고 나오는지 모르겠네요ㅠ

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.lang.Math;

public class Main{
	public static int calculate(int[] arr, int[][] cost) {
		int result = 0;
		for(int i=0;i<arr.length;i++) {
			//System.out.print(arr[i]+" ");
			int a = arr[i];
			int b;
			if(i+1>=arr.length) b = arr[0];
			else b = arr[i+1];
			
			if(cost[a][b]==0) return -1;
			else result+=cost[a][b];
		}
		return result;
	}
	public static int permutation(int[] perm, int[][] cost, int number) {
        int result=calculate(perm, cost);
		int max = -1;
        for(int i=1; i< number; i++) {
        	if(perm[i-1] < perm[i]) max = i;
        }
        	
        if(max==-1) {
        	return 0;
        }
        	
        int max2 = -1;
        for(int j=max ; j<number; j++) {
        	if(perm[max-1] < perm[j]) max2 = j;
        }
        	
        //swap i-1 <-> j
        int temp = perm[max-1];
        perm[max-1] = perm[max2];
        perm[max2] = temp;
        	
        ArrayList<Integer> tempArr = new ArrayList<>();
        for(int i=max ; i<number; i++) {
        	tempArr.add(perm[i]);
        }
        	
        Collections.reverse(tempArr);
        
        for(int i=max; i<number; i++) {
        	perm[i] = tempArr.get(i-max);
        }
        return result;
	}
	public static int factorial(int n) {
		if(n==1) return 1;
		else return n*factorial(n-1);
	}
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
    	int number = in.nextInt();
    	
    	int[][] cost = new int[number][number];
    	for(int i=0; i<number; i++) {
    		for(int j=0; j<number; j++) {
    			cost[i][j] = in.nextInt();
    		}
    	}
    	
    	int t = factorial(number);
    	int[] arr = new int[number];
    	for(int i=0;i<number;i++) {
    		arr[i] = i;
    		//System.out.print(arr[i]+" ");
    	}
    	
    	int result = 1000000;
    	for(int i=0; i<t;i++) {
    		int temp = permutation(arr, cost, number);
    		//System.out.println("temp : "+temp);
    		if(result>temp && temp!=-1 && temp!=0) {
    			result=temp;
    		}
    	}
    	System.out.println(result);
    }
}

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

문제

문제

출처

ICPC

완전탐색을 이용해서 풀었습니다. 반례나 코드 문제점 찾아주세요.

rhdtha01 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말