[9주차_수요일] 외판원

[Jewan1120]

• 사이트 : 백준(BOJ)
• 문제: 외판원
• 번호: 2098

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

이 문제는.. 모르면 못 푸는 전형적인 문제인 것 같아요.. 새로운 개념 같이 공부합시다!

[baexxbin]

🤔 시간복잡도 고려사항

• 2 ≤ N ≤ 16
• 각 행렬의 성분은 1,000,000 이하 (10^6)
• 완전탐색 불가
• 메모리제이션을 이용한 TSP 구현: O(N*2^N)
  • N개의 도시, 방문해야할 도시 2^N
  • 이를 보다 효율적으로하기 위해 비트마스킹 이용

💡 풀이 아이디어

• to번째 도시까지 왔다고 가정한 후, 최적의 값 구하기
  • dp[fm][msk] : 현재 fm도시에서 msk만큼 도시들을 방문한 상태일때, 방문하지 않은 나머지 도시를 돌아 처음도시로 갈때의 최소값.
  • msk
  • 비트마스킹 내용
  • dp배열의 msk는 FULLBIT = (1 << N) - 1;로 모든 도시 N개를 방문한 값의 크기로 선언
• 순회문제이므로, 시작점 고정 가능
• dfs
  • 모든 도시를 방문 했을경우, 마지막도시에서 처음도시 경로 값 반환 (처음 도시를 가지 못할 경우 INF값 반환)
  • 이미 계산해둔 값일 경우, 메모리제이션 내용 반환
  • 다음 도시 이동시, dp[fm][msk] = INF 후 진행
    • dp 초기화를 -1로 해줬기에, 올바른 최소값을 구하기위해 INF로 변경
    • 이때 초기화한 -1은 방문여부 체크역할 진행
    • 또한, dfs반환 및 최소값 계산 과정에서 INF에 값을 더하는 연산이 발생하기에 오버플로우 방지를 위해 Integer.MAX_VALUE 보다 작은 값 이용
• 비트연산
  • 다음 도시 방문 여부 체크 : if ((msk & (1 << to)) != 0)
    • 이때 (msk & (1 << to)) == 1)은 안됨!!!
    • 단순히 to번째 값이 1로 바뀌었는지 체크하는 것이아닌, 전체 값을 확인하는 것이기에 !=0으로 체크하기
  • 다음 도시 방문: msk | (1 << to)

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : 2<=N<=16 -> 16! 완전 탐색 불가 -> DP + 비트마스크 -> 16 2^16 => `O(N 2 ^N)` 가능

💡 풀이 아이디어

• 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램

• 각 도시의 방문 상태가 리스트로 표현됨 -> 변수 1개로 표현 -> bit(이진수 표현)

  • D[2][1, 2] : 현재 도시(2), 1, 2, 도시 방문한 상태에서 나머지 모든 도시를 경유하는데 필요한 최소 비용
  • 4번, 1번 방문 -> D[i][4,1] -> 9 = 1001(2)-> D[i][9]

• 점화식

  D[c][v] = Math.min(D[c][v], D[i][v | (1<<i)] + W[c][i])

• D[c][v] : 현재 도시(c)가 현재까지 방문한 모든 리스트가 v일 때 앞으로 남은 모든 도시를 경유하는데 필요한 최소 비용

• D[i][v | (1<<i)] : i번째 도시 방문 저장

  • 2번째 도시 방문 상태 추가 : v | (1<<2)

• W[c][i] : 현재 도시(c) ~ 다음 도시(i)로 가기 위한 비용

 public static int tsp(int c, int v) {
        if(v==(1<<N)-1){ // 모든 노드를 방문할 경우
            return W[c][0] == 0 ? INF : W[c][0]; // 시작 도시(0)로 돌아감 (돌아갈 수 없으면 INF 반환)
        }
        if(d[c][v] !=0){ // 이미 방문한 노드라면
            return d[c][v]; // 바로 반환
        }
        int min_val = INF;
        for(int i=0; i<N; i++){
            if((v&(1<<i))==0 && W[c][i] !=0){ // 방문한 적 없고 갈 수 있는 노드라면
                min_val = Math.min(min_val, tsp(i, (v | (1 << i))) + W[c][i]); // 현재도시(c) -> 다음 도시(i) 최소 비용 계산
            }
        }
        d[c][v] = min_val;
        return d[c][v];
    }

[yeongleej]

🤔 시간복잡도 고려사항

• 도시의 개수 N <= 16

1) 완전탐색으로 모든 도시 탐색하는 경우 => N! == 16! : 10억 -> 시간초과

2) DP, 비트마스킹 활용 => 도시 방문 : O(N N) => 방문처리 : O(2^N) => O(NN * 2^N) 가능

💡 풀이 아이디어

• 비트마스킹 활용
  • << 연산: 비트를 왼쪽으로 이동 예) (1<<5) == 100000(2) == 32(10) 1) 최대 크기 정하기
    • N = 5일때, 모든 노드를 방문했다면 11111(2)가 되야하므로
    • 10진수로 최대 비트마스킹 크기는 : (1<< N) 2) 방문처리 하기
    • visited : 방문처리 비트마스킹 변수
    • visited | (1 << i) : i번째 노드를 방문처리하기
    • 예) visited = 1011(2), i = 2일때, (1011 | 0100) == 1111(2)이 되므로 i번쨰 노드가 방문처리됨 3) 방문 여부 확인하기
    • visited & (1 << i) : i번쨰 노드를 방문하지 않았다면 0 (0이상은 방문한 노드임)
    • 예) visited = 1011(2), i = 2일때, (1011 & 0100) ==0000(2)이므로 방문하지 않은 노드가 됨
• dp[i][j] = i -> j로 가는 최소 비용
• dfs로 0번쨰 노드부터 출발해서 모든 노드 탐색하기

  // now: 현재 탐색 노드
  // visited: 방문한 노드 체크하는 비트마스킹 변수
  1. 0번쨰 노드부터 시작 : now=0, visited = 1(10)
  2. 모든 노드를 방문했다면 w[now][0]을 반환하고 종료
  3. dp[now][visited]가 이미 방문한 곳이라면 해당 값 반환
  4. 그렇지 않다면 now에서 다음 방문할 노드 찾음
  5. 방문하지 않고 갈 수 있는 i 번째 노드가 있다면 방문
  `dp[now][visited] = min(dp[now][visited], dfs(i + next) + w[now][i])`
  - 이때, next = viisted | (1<< i) : i를 방문처리한 비트마스킹 

INF 값을 Ingteger.MAX_VALUE 로 하니깐 오버플로우나서 헤맸습니다,,,ㅎㅎㅎㅎ

[KodaHye]

🤔 시간복잡도 고려사항

• 외판원 순회 비용: 모든 마을을 방문해서 원래 지점으로 돌아왔을 때, 구하는 최소비용
• 모든 마을을 방문할 때, 순서를 지정하는 경우의 수: n!
  • N: 16 → 20,922,789,888,000 (시간초과)
• DP 방식으로 문제 풀이를 할 수 있음: O(n * 2^n)
  • dp[now][visitedCities]
  • now: 현재 위치하고 있는 도시 번호
  • visitedCities: 방문한 도시들 번호를 이진수로 변환해서 or 한 결과값
    • visitedCities에 대한 정보를 정수를 통해 나타내면 boolean 배열을 사용하지 않아도 효율적으로 방문 처리를 할 수 있음

💡 풀이 아이디어

• int[][] W: 도시를 이동하는데 걸리는 비용 정보
• int[][] dp
  • dp[i][j] 값은 모두 -1로 초기화
  • INF로 초기화할 경우, 한 지점에서 다른 지점을 가지 못하는 경우 방문 여부를 확인해줄 수 없음 (갈 수 없어서 INF인지 방문하지 않아서 INF인지 구분 불가)
  • dp[now][visitedCities]: 현재 now 위치에 있을 있으며, visitedCities에 해당되는 도시들을 다녔을 때 비용의 최솟값
  • visitedCities 사용 예시 (N: 5일 경우)
  • 00001(2): 1번 도시 방문
  • 00010(2): 2번 도시 방문
  • 00100(2): 3번 도시 방문
  • 01000(2): 4번 도시 방문
  • 01101(2): 1, 3, 4 도시 방문(십진수 변환: 13)
  • 11111(2): 모든 도시 방문(1 << 5 - 1 )

외판원 순회 문제 꼭 풀어봐야지,,, 하다가 일년이 넘은거 같은데,, 이제야 풀어보네요!!! 좋습니다👍 그리고 이 블로그에 비트마스킹 정리가 아주 잘 되어 있더라구요! 이거 보면 비트마스킹에 대한 내용에 도움 많이 될 것 같습니다!

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ N ≤ 16 → 모든 조합을 고려한다면 N!... 은 안됩니다.
• 원래 지점으로 돌아옴 + DP를 이용한 그래프 순회 → 외판원 순회 알고리즘

💡 풀이 아이디어

• 외판원 알고리즘 → DFS의 일종
• DP의 메모이제이션을 이용해서 모든 경로를 다시 체크하는 것이 아닌 계산된 값을 가져와서 사용
• DP배열 초기화: -1로 초기화 하여 갱신되지 않았음을 표시

  dp = new int[n][1 << n];
  for (int i = 0; i < n; i++)
      Arrays.fill(dp[i], -1);

• DFS를 이용하여 city → nextCity 로 가는 가중치를 구해주며 최솟값 찾기

• 비트마스킹으로 어떤 도시를 방문했는지 확인하며 해당 도시에서 가지는 방문값(비트마스킹)을 최소로 갱신

  // 외판원 순회
  // @param city 현재 도시
  // @param visited 비트마스킹 방문처리
  private static int tsp(int city, int visited) {
      // 모든 도시를 방문했다면
      if (visited == (1 << n) - 1)
          // 원래 도시로 돌아가는 거리를 반환
          return distance[city][0];
  
      // 미리 계산된 최솟값이 있다면 반환
      if (dp[city][visited] != -1)
          return dp[city][visited];
  
      int result = INF; // 해당 도시를 방문했을 때 최솟값을 구하기 위한 변수
      for (int nextCity = 0; nextCity < n; nextCity++) {
          // 방문한 도시라면 건너뜀
          if ((visited & (1 << nextCity)) != 0)
              continue;
          // 다음 도시를 방문
          int temp = distance[city][nextCity] + tsp(nextCity, visited | (1 << nextCity));
          // 해당 도시에서 가질 수 있는 최솟값 갱신
          result = Math.min(result, temp);
      }
  
      // 계산된 값으로 메모이제이션
      dp[city][visited] = result;
      return result;
  }

  방문처리에 비트연산은 생각보다 많이 쓰인답니돠!

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: dfs, dp, 비트마스킹
• 시간복잡도: 2 ≤ N ≤ 16 출발점 부터 모든 N개의 도시를 재귀적으로 탐색하면서 방문 가능한 모든 도시를 순회하므로 O(N*2^N) 시간복잡도 소요

💡 풀이 아이디어

• DFS 탐색 현재 지점에서 다음 지점까지의 최단거리를 찾으며 다시 처음 도시로 돌아와야 한다 (단순 DFS 만으로는 마지막 도시 > 처음도시로 순환 불가)

• 아무곳에서 출발해도 모든 구간을 순회하고 다시 출발지점으로 돌아와야 하는데, 어느곳에서 시작하든 출발 지점 > 모든 도시 순회 > 출발지점 의 비용은 동일하다

• DP DFS 로 탐색하면서 중복된 순서로 도시을 순회하는 경우가 생기는데, 똑같은 연산을 할 필요가 없기 때문에 메모리제이션을 통해 이미 계산된 값을 가져온다

  • 가능한 모든 도시를 방문하는 경우의 수는 2^N 개로 1<<N 만큼의 dp 배열을 가지고 1,0 로 각 도시에 대한 방문체크를 한다
  • 예) N = 2인 경우, 방문 상태는 00, 01, 10, 11로 총 4가지

• 비트마스킹

  • 방문 체크를 비트연산을 통해 진행하며 방문한 도시는 1, 방문하지 않은 도시는 0 으로 표현

    // 방문 처리: visited 의 next 번째의 자릿수에 1로 방문 표시
    visited | (1<<next)
    // 방문 유무 확인: visited 의 next 번째의 자릿수가 1 이라면 십진수로 변환 시 0 이상이 됨
    visited & (1<<next) > 0