http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030
JUNGOL | 해밀턴 순환회로 > 문제은행
제한시간: 1000 ms 메모리제한: 64 MB 해결횟수: 3023 회 시도횟수: 9435 회 태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다. 오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다. 배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다. 그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 어
www.jungol.co.kr
import java.io.BufferedReader;
import java.io.IOException;
import java.io.StringReader;
import java.util.StringTokenizer;
/**
* @author itsme
* @Date : 2019. 3. 8.
*/
public class Main_JA_1681_해밀턴순환회로_조용준 {
// TODO: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030
// 노드간 이동 비용이 0인 점은 이동할 수 없다.
// 언제나 1번 부터 시작해서 1번에서 종료한다.
private static int N; // 1번 지점부터 시작할 수 있도록 입력 값보다 1 크게 처리
private static int[][] map;
private static int MIN_COST = Integer.MAX_VALUE;
// 순서가 있는 상태에서 갈 수 있는 모든 경로를 다 가볼 것 >> 순열
private static int[] visited;
private static int[] path;
public static void main(String[] args) throws NumberFormatException, IOException {
input();
visited = new int[N];
path = new int[N];
path[1] = 1; // 패스 초기화 언제나 1부터 시작한다.
npr(2, 0);
System.out.println(MIN_COST);
}
// 비용을 모니터링하기 위해서 계속 가지고 다닌다.
public static void npr(int toIdx, int cost) {
if (toIdx == N) { // 마지막 지점까지 감 --> 이제 다시 회사로 복귀만 확인
int lastCost = map[path[toIdx - 1]][1];
if (lastCost > 0 && lastCost + cost < MIN_COST) {
//System.out.printf("cnt: %d, temp: %s, cost: %d%n", ++cnt, Arrays.toString(path), cost);
MIN_COST = cost + lastCost;
}
return;
} else {
for (int nextPlace = 2; nextPlace < N; nextPlace++) {
if (visited[nextPlace] == 0) {
int thisCost = map[path[toIdx - 1]][nextPlace]; // 이동에 드는 추가 비용 계산
if (thisCost > 0 && cost + thisCost < MIN_COST) { // 추가비용이 0원 이상이고 비용의 합이 최소보다 작아야 의미있다.
visited[nextPlace] = 1;
path[toIdx] = nextPlace;
npr(toIdx + 1, cost + thisCost);
visited[nextPlace] = 0;
}
}
}
}
}
// 입력 처리
private static void input() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new StringReader(src));
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()) + 1;
map = new int[N][N]; // 회사가 1번이므로 1씩 크게 잡아줌
for (int r = 1; r < N; r++) {
StringTokenizer tokens = new StringTokenizer(br.readLine());
for (int c = 1; c < N; c++) {
map[r][c] = Integer.parseInt(tokens.nextToken());
}
}
// 입력 확인
/*
* for(int [] row: map) {
* System.out.println(Arrays.toString(row));
* }
*/
}
// 정답: 101
static String src = "6\r\n" +
"0 93 23 32 39 46 \r\n" +
"0 0 7 58 59 13 \r\n" +
"40 98 0 14 33 98 \r\n" +
"3 39 0 0 13 16 \r\n" +
"51 25 19 88 0 47 \r\n" +
"65 81 63 0 6 0 ";
}