글 읽기 - 외판원순회 문제 왜 틀리는지 모르겠습니다

leeho203 7년 전 0

이 문제를 3시간 넘게 붙잡고 있는데 도대체 왜 틀린지 잘 모르겠습니다

고수님들 제발 부탁드려요ㅠㅠ

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

public class Main {
	static int V;
	static int[][] adj;
	static int[][] cache;
	static int end;

	public static void main(String args[]) throws IOException {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		adj = new int[V + 1][V + 1];
		cache = new int[V + 1][1 << (V + 1)];

        // 인접행렬 데이터 입력
		for (int i = 1; i <= V; i++)
			for (int j = 1; j <= V; j++) {
				adj[i][j] = sc.nextInt();
				if (adj[i][j] == 0)
					adj[i][j] = 987654321;
			}

		for (int i = 0; i < cache.length; i++)
			for (int j = 0; j < cache[i].length; j++)
				cache[i][j] = -1;

		int answer = Integer.MAX_VALUE;
		for (int i = V; i >= 1; i--) {
			end = i;
			answer = Math.min(answer, shortestPath(i, 1 << (i - 1)));
		}

		System.out.println(answer);

	}

	static int shortestPath(int here, int visited) {
		int result = 987654321;

		// 모든 도시를 다 방문했다면 첫 번째 도시로 돌아가고 종료
		if (visited == ((1 << V) - 1))
			return adj[here][end];

		if (cache[here][visited] != -1)
			return cache[here][visited];

		for (int next = 1; next <= V; next++) {
			// 해당 도시를 이미 방문했다면 더이상 방문하지 않음
			if ((visited & (1 << (next - 1))) >= 1)
				continue;
			result = Math.min(result, adj[here][next] + shortestPath(next, visited + (1 << (next - 1))));
		}

		return cache[here][visited] = result;
	}
}

WeissBlume 7년 전 2

라인 29에서 시작되는 루프 안에서도 cache를 초기화해야 합니다.

근데 사실 이건 사이클이라서 어디서 시작해도 답이 같기때문에 굳이 루프를 돌 필요가 없어요.

leeho203 7년 전 0

아 그런 것이군요!! for문 지우고 한 번만 돌게 수정하니깐 바로 AC뜨네요ㅋㅋㅋ

덕분에 많이 배워갑니다 감사합니다~~~!!

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

문제

문제

출처

ICPC

외판원순회 문제 왜 틀리는지 모르겠습니다

leeho203 7년 전 0

WeissBlume 7년 전 2

leeho203 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말