글 읽기 - 주어진 input으로는 맞는데, 채점결과가 틀려요,.

nhe1229 6년 전 0

문제에서 주어진 input으로는 35가 맞게 나오는데,

채점결과는 틀리네요

어디가 틀렸는지 모르겠어요.

import java.io.FileInputStream;
import java.util.Scanner;
public class Main {
 static int N, startP;
    static int[][] W;
    static int[] visited;
    static int min_cost = 100000001;
    public static void backtrack(int n, int cost, int cnt)
 {
  if (cost >= min_cost) return; //가지치기 - 이미 구한 min값보다 현재 비용이 클때 바로 종료.
  
  if (n == startP && cnt == N) //종료조건 - 1번노드로 방문했을때 전체 순회 카운트가 N이면 모든 정점을 돌고 1번노드로 방문한 상태임
  {
   //System.out.println("COST :  " + cost);
   if (min_cost > cost) min_cost = cost;
   return;
  }
  
  
  for (int i = 1; i <= N; i++) {
   //현재 정점n에서 갈수있는 visited되지 않은 정점들을 방문해야함
   if(visited[i]==0 && W[n][i]!=0 ){
    visited[i]=1;
    cost += W[n][i];
    backtrack(i, cost, cnt+1);
    visited[i]=0;
   }
  }
  
 }
    public static void main(String[] args) throws Exception {
     
     //System.setIn(new FileInputStream("C:\\inputSamples\\sample_input_travelingCity.txt"));
     Scanner sc=new Scanner(System.in);
     N=sc.nextInt();
        W = new int [N+1][N+1];
        visited = new int [N+1];
        
        //1~N 
        for (int i=1;i<=N;i++) {
            for (int j=1;j<=N;j++) {
                W[i][j]=sc.nextInt();
                //System.out.print(W[i][j]+"  ");
            }//System.out.println();
        }
        
   
        
        for(int i=1; i<=N; i++){
     for (int j=1; j<=N; j++)
      { 
      //현재 정점이 1번이라고 가정하고 방문할 수 있는 모든 경우에 대해 백트래킹을 호출하면서 시작
      visited[j] = 1;
      startP = i;
      backtrack(j, W[i][j], 1); 
      visited[j] = 0;
      }
        }
        
        
     System.out.println(min_cost);
    }
}

zlzmsrhak 6년 전 0

해결 달아주세요

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

문제

문제

출처

ICPC

주어진 input으로는 맞는데, 채점결과가 틀려요,.

nhe1229 6년 전 0

zlzmsrhak 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말