글 읽기 - 외판원 순회2 문제 자체에 대해 질문이 있습니다.

gusdn7236 3년 전 0

문제에서 길이 없으면 0으로 표시한다고 했는데, 막약 0 -> 4로 가는 길이 0이면 4 -> 0으로 가는 길도 0인가요??

일단 코드는 배열의 인덱스와, 배열에 다음 인덱스를 담아서 처리하였는데, 계속 틀리다고 나오네요.

혹시나 질문처럼 0 -> 4로 가는길은 없는데, 4 -> 0으로 가는 길이 있는 예시가 존재할 수 있다고 생각을 해야하는지 궁금하네요.

import java.io.*;
import java.util.StringTokenizer;

class Main {
    public static int[][] input;
    public static boolean[] choice;
    public static int[] ret;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        input = new int[n][n];
        choice = new boolean[n];
        ret = new int[n];
        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int idx = 0;
            while(st.hasMoreTokens()) input[i][idx++] = Integer.parseInt(st.nextToken());
        }
        choice[0] = true;
        System.out.println(solve(0));
    }
    
    public static int solve(int start){
        boolean finished = true;
        for(boolean el : choice) if(!el) finished = false;
        int sum = 987654321;
        if(finished){
            sum = 0;
            int cnt = ret.length;
            int idx = 0;
            while(cnt-- > 0){
                sum += input[idx][ret[idx]];
                idx = ret[idx];
            }
            return sum;
        }

        for(int end = 1; end < ret.length; end++){
            if(choice[end] || start == end || input[start][end] == 0)
                continue;
            else{
                ret[start] = end;
                choice[end] = true;
                sum = Math.min(sum, solve(end));
                choice[end] = false;
                ret[start] = 0;
            }
        }
        return sum;
    }
}

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

문제

문제

출처

ICPC

외판원 순회2 문제 자체에 대해 질문이 있습니다.

gusdn7236 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말