비트마스크 활용 (백준 2098 외판원순회)

비트 마스크란?

비트는 컴퓨터에서 다루는 최소 단위이다.

정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크 라고 한다

프로그래밍을 하며 비트마스크가 왜 필요한지 알아봤다.

• 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐
• 더 간결한 코드 작성이 가능
• 더 빠른 연산이 가능
• 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함

사실 4번 DP를 활용하기 위해 파이썬을 이용해서 비트마스크를 쓰는 방법을 연습했다.

DFS를 할때 내가 방문했던 곳들의 상태를 저장하기 까다로울텐데 비트마스크를 쓰면 간단하게 쓸 수 있다.(n이 작다면)

 

파이썬에는 bin함수가 내장되있어서 쉽게 2진수로 출력이 가능하다

기본 계산

AND연산
bin(0b1010011010 & 0b1101101100)  # 0b1000001000
OR연산
bin(0b1010011010 | 0b1101101100)  # 0b1111111110
XOR연산
bin(0b1010011010 ^ 0b1101101100)  # 0b111110110
SHIFT연산
bin(0b0010 << 2)  # 0b1000
bin(0b1100 >> 2)  # 0b11
bin(~0b0010 << 2)  # 0b1101
~NOT연산
bin(~0b0010 << 2)  # 0b1101

그리고 중요한 스킬들

#원소 추가
n = 3
print(bin(0b0010 | (1 << n)))  #  0b1010
#원소 제거
n = 3
print(bin(0b1010 & ~(1 << n)))  #  0b10
#원소 조회
n = 3
print(bin(0b1010 & (1 << n)))  #  0b1000
#원소 토글 (XOR)
n = 3
print(bin(0b1010 ^ (1 << n)))  #  0b10

이러한 스킬들을 공부하고 다음 두 문제를 풀어봤다.

이진수연산 https://www.acmicpc.net/problem/12813

집합 https://www.acmicpc.net/problem/11723

집합 문제를 풀때는 bin을 사용하면 문자열이 되버린다는 것을 몰라서 애를 먹었다

 

마지막으로 비트마스크를 공부한 이유인 2098번을 풀어보았다.

외판원 순회(2098)

https://www.acmicpc.net/problem/2098

1.접근

DP와 DFS를 활용한다

2.풀이

모든 경로를 DFS를 이용하여 탐색한다. 탐색을 하면서 방문했던 곳은 visit를 비트마스크로 표현하여 간단하게 표기한다.

일단 문제를 풀려면 순회하는 경로를 찾아야 하므로 1에서 N으로 가는 모든경로를 찾고 마지막에 다시 1로 돌아오게 되는 경로까지 더한것의 최솟값을 찾아야한다 (순환하므로 시작점을 어디로잡아도 상관없다).

이대로 풀면 DFS를 많이 반복하면서 시간이 오래걸리므로 DP를 써줘야한다.

점화식은 내가 현재 와 있는곳과 방문했던 곳을 기반으로 방문하지 않은곳들 경로 합의 최솟값을 구해갔다.

n이 4라고 가정해보자(0,1,2,3)

0에서 시작해서 2로갔다고 생각해보자

visit은 0101이 되고 갈수있는곳은 1,3 현재위치는 2이다

여기서 1101이 될 수도 0111이 될 수도 있다. 따라서 다음에 나올 dp[3][1101]+adj[2][3] 과 dp[1][0111]+adj[2][1]값중 더작은 값을 dp[2][0101]로 둘 수 있을것이다.

모든 구간을 방문했을때는 다시 돌아가는 값을 리턴해줘야한다

이미 방문한 곳일 때는 그대로 리턴해준다.

이렇게 dfs와 dp를 섞어서 코드를 짜줘야한다.

3.코드

4.배운점

• 처음에 순회 한다는 개념이 익숙하지 않아서 모든 시작점을 고려해야한다고 생각했다.
• visit&(1<<i)같은 비트마스크 표현이 너무 어색했지만 이제 잘 쓸 수 있을거 같다. 같은 코드를 비슷하게 3~4번정도 연습해봤다
• DFS와 DP가 섞여서 머리에서 구상하기 너무 힘들었다. dp를해서 앞에서부터 구하는게 아니고 뒤에 남은 값들을 합친다는 생각을 하기 어려웠다.
• DP는 어렵다

https://justkode.kr/algorithm/bitmash 님의 포스팅을 보고 공부했습니다