알고리즘이라기엔... 음 비트를 활용한 테크닉이라고 봐야함!
🔵 비트마스크(Bitmask)란?
비트 단위로 값을 보존하는 것.
◼ 비트 연산을 통해 삽입, 삭제, 조회 하는 법
◾ 삽입 : 1010 => 1110 (i번째 비트 1로 변경하기)
A | (1 << i)
1010 | (1 << 2) = 1010 | 0100 => 1110
-> 시프트 연산을 통해 i번째 비트만 1로 할당되어있는 이진수를 만든다.
그리고 OR연산을 통해 원하는 결과를 만들어준다.
◾ 삭제 : 1110 => 1010 (i번째 비트 0으로 변경하기)
A & ~(1 << i)
1110 & ~(1 << 2) = 1110 & 1011 => 1010
-> 시프트 연산을 통해 i번째 비트만 0 (== ~1)으로 할당되어있는 이진수를 만든다.
그리고 AND연산을 통해 원하는 결과를 만들어준다.
◾ 조회
A & (1 << i)
2번째 비트 - 1010 & (1 << 2) = 1010 & 0100 => 0
3번째 비트 - 1010 & (1 << 3) = 1010 & 1000 => 1000
-> AND연산과 시프트연산을 통해 i번째 비트의 값이 0이라면 값이 0이라는 것을 알 수 있다.
⚫ 비트마스크를 활용한 예
! 대표 문제 "외판원 순회 (TSP)"
-> DP에 비트마스크를 접목한 방식
문제
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j] = 0이라고 하자.
N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.
즉, 모든 도시를 한번씩만 방문하며 다시 시작점으로 돌아오는 최소 거리 비용을 구하는 문제이다.
점화식은
dp[curr][visited] = min(dp[curr][visited], tsp(next, visited + next) + w[curr][next])
현재 도시가 curr이고, 방문한 도시들의 집합이 visited일 때, 나머지 도시들을 순회한 최소 비용이다.
여기서 visited를 배열로 관리하는 것이 어렵기에, 비트마스크를 활용하는 것이다.
도시가 0~3번까지 존재할 경우
0번 3번 도시를 들렸다는 것은 1001로 표현할 수 있고, 정수로는 9를 의미한다.
즉, 2번 도시에서 0번, 3번을 방문하고 순회했을 때의 최소비용이 dp[2][9]인 것이다.
출처 : 마이구미의 HelloWorld
위처럼 dp[3][00001111]에 모든 도시를 순회한 최소 비용을 구했다고 가정한다.
그렇다면, dp[3][00001111]에 해당되는 것들은 나머지 도시들을 방문하지 않고, 이 최소비용을 재사용하면 된다. 여기서 dp[3][00001111]의 경로는 다음과 같다.
0 -> 1 -> 2 -> 3 -> .....
0 -> 2 -> 1 -> 3 -> .....
0 -> 3 -> 1 -> 2 -> .....
0 -> 3 -> 2 -> 1 -> .....
출처 : 마이구미의 HelloWorld
위와 같이 부분적으로 문제를 나누어 해결하였다. 여기서 사용되는 비트 연산은 다음과 같다.
▪ 모든 도시를 방문한 경우 (모든 비트의 값이 1인지 판단)
▪ 이미 방문한 도시 여부 (i번째 비트의 값이 1인지 판단)
▪ 다음 도시를 방문했을 경우 (i번째 비트의 값을 1로 변경)
💙 스터디 예제
◼ ch15
🔘V 11723 집합
🔘V 1094 막대기
🟡III 10736 XOR삼형제 2
🔘II 10971 외판원 순회2
🟡I 1194 달이 차오른다, 가자.
🟡I 2098 외판원 순회
🟡IV 1322 X와 K
🟡I 2825 수업시간에 교수님 몰래 교실을 나간 상근이
🟡IV 1062 가르침
🟡I 21321 클레이 사격 게임
🔘II 15787 기차가 어둠을 헤치고 은하수를
🟡IV 2830 행성 X3
