[JO] 1681 해밀턴 순환회로 - JAVA

1. 문제

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=99&sfl=wr_hit&stx=1681

JUNGOL

---

2. 풀이

첫번째를 이미 방문했다고 치고(=회사), cnt와 flag를 1로 넣어서 함수를 호출했다.

기저조건

• cnt가 N과 동일하면 끝낸다. 마지막으로 방문한 곳(prev)가 회사로 가는 길이 없다면 바로 종료한다.
• 지금까지 구한 sum에 회사로 가는 비용을 더해서 전체의 MIN값과 비교해 저장한다.

유도조건

• 1) 방문한 곳이거나 2) 직전 집에서 i번째 집으로 오는 길이 없다면, 3)지금까지의 sum에 [직전 집에서 i번째 집으로 오는 비용]을 더한 값이 MIN값보다 이미 크다면 탐색하지 않는다.
• 위의 경우가 아니라면 재귀호출한다.

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

public class JO_1681_해밀턴순환회로 {
   static int N, MIN = Integer.MAX_VALUE;
   static int[][] map;

   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());

      map = new int[N][N];
      StringTokenizer st;
      for (int i = 0; i < N; i++) {
         st = new StringTokenizer(in.readLine());
         for (int j = 0; j < N; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
         }
      }

      find(1, 0, 0, 1);

      System.out.println(MIN);

   }

   private static void find(int cnt, int prev, int sum, int flag) {
      if (cnt == N) {
         if (map[prev][0] == 0) return;
         sum += map[prev][0];
         MIN = Math.min(MIN, sum);
         return;
      }

      for (int i = 1; i < N; i++) {
         if ((flag & 1 << i) != 0 || map[prev][i] == 0 || sum + map[prev][i] > MIN) continue;
         find(cnt + 1, i, sum + map[prev][i], flag | 1 << i);
      }
   }
}

---

3. 결과

고객의 집을 한 번씩만 방문해야한다길래 배달할때만 그런 줄 알고 다익스트라 탐색과 혼합해서 풀었더니 45점이 나왔다. 그냥 다 방문했을때 바로 회사가면 된다.

기저조건에서 직전집->회사로 가는 길이 없을 수도 있다는 점을 빼먹을 뻔 했다. 어쩐지 계속 틀렸는데 스터디 팀원이 이거저거 잘 알려주셨다!