글 읽기 - 도와주세요 ㅠㅠㅠ

bgd0706 5년 전 0

머가 틀렸는지 모르겟네요 ㅠ

0 0 10 10

10 0 3 10

10 10 0 3

3 10 10 0 에서도 33이 나오고, 예제에서 35가 나오고

시작하는 점은 상관없어서 0으로 시작한다고 정해놨어요....

import java.util.Scanner;

public class BJ45 { // 10971 - 해결못함 
	
	static int check [];
	static int price [][];
	static int min = 2147483647;
	static int sum = 0;
	static int num;
	static int stand = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		
		num = input.nextInt();

		price = new int [num][num];
		check = new int [num];
		
		for (int i = 0 ; i<num ; i++) {
			for (int j=0;j<num;j++) {
				price[i][j] = input.nextInt();
			}
		}
		
		check[stand]=1;
		dfs(stand, 0);
		
		System.out.println(min);
		
	}
	public static void dfs(int x, int y) { 
		if (y == num-1) {
			sum+= price[x][stand];
			if (min > sum) {
				min = sum;
			}
			sum-= price[x][stand];
			return;
		}
		
		for (int i=0 ; i<num ; i++) {
			if (check[i] == 1) continue;
			
			if (price[x][i]!=0) {
				check[i]=1;
				sum += price[x][i];
				dfs(i, y+1);
				sum -= price[x][i];
				check[i]=0;
			}
		}
		
	}
}

hyunynim 5년 전 0

35번줄에

sum+= price[x][stand] 에서

x -> stand로 가는 경로가 없다면 문제가 생길것 같아요

hyunynim 5년 전 0

4
0 1 2 0
1 0 2 0
0 0 0 3
0 2 0 0

이 경로는

1 -> 2 -> 3 -> 4 -> 1이 불가능하고

1 -> 3 -> 4 -> 2 -> 1로 돌아와야 합니다.

bgd0706 5년 전 0

x -> stand 경로를 따로 안한것은 이미 sum에 포함되도록 했기 때문에 그렇게 한겁니다.

그리고 1 -> 2 -> 3 -> 4 ->1 로 안가기 위해

if (price[x][i]!=0) 이란 조건을 달앗어요

hyunynim 5년 전 1

@bgd0706

34번줄 구문

if(y == num - 1)

이 부분이 의미하는게 1-> 2-> 3-> 4 인 상황을 얘기하는게 아닌가요?

이상태에서 4 -> 1로 가는 경로가 없을 때에도 있다고 생각하고 탐색이 진행됩니다.

hyunynim 5년 전 0

저 구문에 경로가 없을 경우 답을 갱신시키지 않는 구문을 추가하면 AC를 받습니다.

bgd0706 5년 전 0

감사합니다.

if ( y == num-1) 이 부분에도 한 조건을 했어야 했네요

정말 감사합니다.

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

문제

문제

출처

ICPC

도와주세요 ㅠㅠㅠ

bgd0706 5년 전 0

hyunynim 5년 전 0

hyunynim 5년 전 0

bgd0706 5년 전 0

hyunynim 5년 전 1

hyunynim 5년 전 0

bgd0706 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말