비트마스킹(Bit Masking)

목차

비트마스킹(Bit Masking)

• 비트마스킹은 일종의 기술입니다.
• 이진수 표현을 활용해 값을 저장하거나 연산하는 기법으로 빠른 연산이 가능합니다.
• 비트 연산자 종류
  • and(&) : 둘 다 1이여야지 1 / 나머지 0
  • or(|) : 둘 중에 한 개라도 1이 있다면 1 / 둘다 0일 경우 0
  • xor(^) : 둘 중에 한개만 1일 경우 1 / 둘다 1이거나 0일 경우 0
  • not(~) : 1인 것은 0으로 0인것은 1로 변환
  • 왼쪽 쉬프트(<<) : A<<n 은 A를 2**n로 곱한것
  • 오른쪽 쉬프트(>>) :  A>>n  은 A를 2**n으로 나눈것
• 비트 연산자의 활용 예시
  • 특정 mask에 n번째 비트값이 1인지 확인하기
    • 1<<3을 예시로 들면 1000 이 됩니다. 즉 1000과 & 연산을 할때 mask의 3번째 비트가 1이여야지 1000과 &을 하면 0이 되지 않습니다. (1<<3 이면 0이 3개라고 생각하기)
      • 3번째 비트라고 하는 이유는 비트는 0번째부터 시작합니다.

    • if mask & (1 << n):
          print("n번째 비트는 1입니다.")
      else:
          print("n번째 비트는 0입니다.")

       
  • k번째 비트 키고 싶을때

    • mask = mask|(1<<k)

  • k번째 비트 끄고 싶을때

    • mask = mask&~(1<<k)

  • 모든 비트가 1인지 확인하고 싶을때
    • 비트가 5자리라고 하면 (1<<5)-1과 비교하면 됩니다.

    • mask==(1<<n)-1

  • 모든 비트가 0인지 확인하기

    • mask==0

• 그렇다면 어떤 문제에서 비트연산자가 사용될까요?
  • 가장 대표적인 예시로는 비트 단위로 k번째 물건이 선택되었나/안되었나, k번째 도시를 방문했나/안했나 정도를 표현할때 사용됩니다. 
    • 원래는 visited 를 [] 리스트 안에 넣어서 체크를 진행했는데 이것을 이진법을 사용해서 0000 처럼 표현이 가능합니다. k번째노드 방문처리 -> (1<<k) 이런식으로 처리하게 되면 메모리 측면에서 효율적이게 됩니다. 또한 계산적인 부분에서도 쉬프트 연산자로 빠르게 수행이 가능하므로 효율적입니다.
    • 모든 노드를 방문했는지 체크하고 싶을 경우 (1<<n)-1 하고 비교해보면 됩니다.
  • 현재 위치에 대해서 여태까지 방문한 도시들에 대한 최소 비용을 구할때도 유용합니다.
    • dp[mask][현재위치] 이런식으로도 사용이 가능합니다.
    • 방문 순서에 상관없이, 방문했던곳이 동일하고 현재 위치가 동일하다면 어떤것이 더 빠른지 dp[mask][현재위치] 이런식으로 확인이 가능합니다.
      •  visited를 사용하게 되면 위와 같은 dp는 사용할 수 없습니다.
    • 하지만, dp를 이용할 경우 mask가 2진수 이기때문에 엄청나게 커질수가 있습니다. 따라서 이렇게 사용할 경우는 전체 n개가 작을 경우에만 사용이 가능합니다. (n이 20이하정도일경우)

예시

• [백준 2098] 외판원 순회
  • 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 할때, (단 한번 갔던 도시로는 다시 갈 수 없습니다.) 가장 적은 비용을 들이는 여행 계획을 세우는 방법을 세우는 문제입니다.
  • n개의 도시를 가장 적은 비용이 들도록 나열하는 문제입니다. 즉 최대한 도시 사이의 거리가 짧은 것들로만 다녀야합니다. 
  • 여기서 dp는 dp[현재방문한도시비트][현재위치] 에서 모든 도시를 방문하게된다면 그때 방문할 도시들의 거리의 최소 비용이 됩니다.
    • 재귀의 제일 안쪽은 dp[11111111][현재위치] 에서 출발지점인 0으로 돌아오는 경우가 될것입니다.
    • 따라서 만약에 내가 탐구해서 들어가다가 dp[현재방문한도시비트][현재위치] 값이 None이 아니라면 그 값을 그대로 가져오면 됩니다. 이미 탐구해서 들어간 뒤 해당 지점(현재방문한도시비트,현재비트)에서 출발지점까지 돌아가는 최소비용을 구해놓은 값이기때문입니다.
    • 결국 dp[1][0] 은 현재방문한도시비트가 1이고(0번째도시면 0번째비트가1), 현재 0번째 도시에 있는 상태인데 여기서 다시 출발점으로 돌아올 최소비용을 의미합니다.
  • 외판원 순회는 0번째에서 출발해서 0으로 돌아오나, 1번째에서 출발해서 1으로 돌아오나 최소비용은 모두 동일할 것입니다. (어차피 원을 형성하는 것이기때문에, 최소거리로 연결되는 원을 찾는 것)
  • 출발지점과 최종목적지가 정해져 있는경우 비트마스킹을 이용하여 (현재까지방문한mask, 현재위치)에서 최종목적지까지 도달하기 위한 최소 거리를 dp[현재까지방문한mask][현재위치] 로 표현가능합니다.)
  • 코드

    • n = int(input())
      
      w = [list(map(int, input().split())) for _ in range(n)]
      
      dp = [[None for _ in range(n)] for _ in range(1 << n)]
      
      
      def find(bit, now_point):
          if dp[bit][now_point] != None:
              return dp[bit][now_point]
      
          if bit == (1 << n) - 1:
              if w[now_point][0] == 0:  # 돌아가는 길이 없는 경우
                  return float("inf")
              else:
                  return w[now_point][0]
      
          temp = float("inf")
          for next in range(n):
              if bit & (1 << next) == 0 and w[now_point][next] != 0:
                  temp = min(temp, find(bit | (1 << next), next) + w[now_point][next])
      
          dp[bit][now_point] = temp
          return dp[bit][now_point]
      
      
      print(find(1, 0))