[백준 파이썬 2098번 외판원 순회] 비트마스킹이란 무엇인가?

2098번: 외판원 순회

이전에 외판원 순회2는 손쉽게 풀었던 경험이 있는데

외판원 순회2의 경우 시간 제한도 2초이고 메모리제한도 256MB라 아주 널널했던 것으로 기억한다.

def dfs(depth, start, total):
    global MIN
    if depth == N-1 and graph[start][0] != 0:
        total += graph[start][0]
        MIN = min(MIN, total)
        return

    for i in range(N):
        if not visited[i] and graph[start][i] != 0:
            visited[i] = True
            dfs(depth + 1, i, total + graph[start][i])
            visited[i] = False

 

이런 무식한 dfs로도 풀 수 있었기 때문에 문제 난이도도 실버2였는데

외판원 순회 1은 숫자가 낮아진만큼 시간제한과 메모리 제한도 줄어들어서 빡빡해졌다.

---

DP와 비트마스킹

두 가지 중 하나라도 쓰지 않으면 이 문제는 풀리지 않는데 그 이유는 위에서도 말했듯이 시간과 메모리가 반토막이 되었기 때문이다.

 

DP는 시간을 줄이기 위한 방법
비트마스킹은 사용 메모리를 줄이기 위한 방법

 

DP는 이전 글에서도 많이 언급을 했기 때문에 pass

그렇다면 비트마스킹은 뭘까?

비트마스킹 왜 써요?

비트마스크 (BitMask) 알고리즘

 

외판원 순회2에서는 리스트로 visited를 표현했다면

이를 비트마스크를 통해 구현해서 더 빠르고 간결하고 더 적은 메모리 사용을 얻을 수 있다.

 

이 중 우리는 메모리 사용량이 적다는 것에 주목해야하는데

그 이유는 리스트보다는 bit로 표현하는 것이 훠월씬 메모리 사용량이 적기 때문이다

간단한 예시를 들자면 bit가 10개인 경우에는 각 bit당 두 가지 경우가 생기기 때문에 2^10가지의 경우를 10bit로 표현이 가능하다!

 

참고로 파이썬의 리스트는 굉장히 크다! (4KB = 32000bit)

 

비트마스킹 어떻게 써요?

이 문제의 핵심 코드이다

def dfs(now, visited):
	# 모두 방문했으면 ex) 1111
    if visited == (1 << N) - 1:
    	# 종료코드
	
	min_cost = int(1e9)
    for nxt in range(1, N):
        # print(bin(visited), nxt, bin(1 << nxt), visited & (1 << nxt))
        if graph[now][nxt] == 0 or visited & (1 << nxt):
            continue
        # print("다음 방문지", bin(visited | (1 << nxt)))
        cost = dfs(nxt, visited | (1 << nxt)) + graph[now][nxt]
        min_cost = min(min_cost, cost)

 

여기서 핵심은 and 연산과 or 연산인데

# and 연산
if visited & (1 << nxt):
    continue

# or 연산
dfs(nxt, visited | (1 << nxt))

 

nxt는 n번째 방문지를 의미하고

(1 << nxt)는 n번째 비트를 1로 표현한 비트이다

이를 통해 우리는 visited를 표현할 수 있다

 

그리고 and 연산을 통해 이미 방문한 곳인지 알 수 있고

만약 아직 방문하지 않았다면 or 연산을 통해 이제 방문 했음을 표현할 수 있다

그리고 or 연산을 하면 1111이 되면서 이제 방문했음을 나타낼 수 있다!

 

---

CSAPP의 비트 연산자 파트를 공부할 때 굉장히 고통스러웠던 기억이 있는데 뭔가 코테 문제에서 보니까 반가운 것 같기도하고?