[백준 2098번] 외판원 순회 (비트마스킹) - Python / 시관초과 해결방법
🐳 문제 - [백준] 외판원 순회 (2098번)
이번 문제의 경우 비트마스크 알고리즘 개념에 대해 간단하게 살펴본 후 외판원 순회 문제 풀이에 대해 알아보도록 하자
🐳 알고리즘 - 비트마스크 ( Bitmask )
🎯 Bitmask 란 ?
정수를 컴퓨터처럼 이진수를 이용해 나타내는 것을 의미한다.
예를 들어 10이라는 숫자를 2진수로는 1010 이라고 나타내는 것처럼 정수를 이진수를 통해 나타내는 것이다.
🎯 비트마스크의 장점 및 사용이유
한 가지 예시를 살펴보자
예를 들어 A,B,C,D 라는 네 개의 스위치가 있다고 해보자. 각각의 스위치의 상태는 On 또는 Off 이다.
어떻게 하면 A,B,C,D의 상태를 저장할 수 있을까?
Python의 경주 setOn = set()를 통해 setOn에 켜져 있는 스위치를 add해 줌으로써 구현 가능할 것이다.
이 외에도 다양한 방법이 많지만 비트마스크의 경우 이 문제를 정말 간단하게 해결할 수 있다.
켜져 있는 경우를 1 꺼져 있는 경우를 0 이라고 하면
모든 경우의 수를 0000 ~ 1111 의 숫자로 표현 가능하다.
이렇게 비트마스크를 사용하게 되면 상태를 나타내는 것이 간편해진다.
위의 예시로 살펴본 것처럼 비트마스크의 장점으로는
첫째. 코드를 간결하게 만들 수 있다.
둘째. 메모리 사용량이 적다. 비트마스크의 경우 단순 정수형 자료형 만을 사용하기 때문이다.
셋째. 속도가 빠르다. 비트 연산자의 경우 시간 복잡도가 O(1)이므로 처리 속도가 빠르다.
🎯 비트마스크 사용예시
여기서 한 가지 궁금증이 들었다.
그러면 10이라는 숫자를 이진수 1010으로 바꿔준 후에 다시 비트 연산자를 실행하고 그 후에 다시 십진수로 바꿔야 하는 것일까?
아래의 Python Code를 통해 확인해 보자
a = 10
b = 12
print(a&b)
# &는 and 비트 연산자이다.
결과는 어떻게 될까? 애초에 정수와 정수를 & 한다는 것이 생소하게 느껴질 수 있다.
결과는 8 이다.
왜 그런 것일까 ?
a = 10 = 1010(2)
b = 12 = 1100(2)
그러므로
a&b = 1000(2) = 8 이 된다.
위의 간단한 예재를 통해 확인할 수 있는 것은 정수를 이진수로 바꿔주지 않아도 자동으로 이진수로 바꿔 비트연산자를 수행해 준다는 것이다.
1. & (AND) 연산자
2. | (OR) 연산자
3. ^ (XOR) 연산자
4. ~ (NOT) 연산자
5. <<,>> (SHIFT) 연산자
🎯 비트마스크 연산자
a = 10 = 1010(2)
b = 12 = 1100(2)
1. &(AND) 연산자
a & b = 1000(2) = 8
2. |(OR) 연산자
a | b = 1110(2) = 14
3. ^(XOR) 연산자
a ^ b = 0110(2) = 6
4. ~(NOT) 연산자
이 부분이 가장 헷갈린다.
~a = 0101(2) 이므로 5 일 것으로 예상된다.
근데 결과는 ? -6이라는 숫자가 나온다. 이게 무슨 일일까?
먼저 a = 1010(2) 라고 했지만 Python은 기본적으로 8 bit signed form 을 사용한다.
이는 정수를 8bit로 표현하고 맨 앞자리는 부호를 나타낸다는 것이다.
그러므로 a = 1010(2) 이 아니라 사실은 00001010(2) 인 것이다.
그러므로 ~a = 11110101(2) 가 된다.
이때 맨 앞의 1은 부호를 의미하고 이는 -2**7을 의미한다.
그러므로 계산 결과는
-2**7 + 2**6 + 2**5 + 2**4 + 2**2 + 2**0 이 되므로
-128 + 64 + 32 + 16 + 4 + 1 = -11 이 된다.
5. <<,>>(SHIFT) 연산자
시프트 연산자는 원하는 방향으로 원하는 만큼 비트를 밀어주는 것을 의미한다.
예를 들어 a << 2 의 경우 1010(2) 를 왼쪽으로 2칸 밀게 되므로 101000(2) 가 되어 40이 된다.
🐳 아이디어
🎯 시작지점 아이디어
이 문제의 경우 여행시작 지점을 자유롭게 설정할 수 있다.
0번 지점에서 여행을 시작했다고 가정하고 최단 경로가 0 -> 1 -> 2 -> 3 -> 0 이라고 가정하자
그렇다면 1번 지점에서 여행을 시작하게 되면 최단 경로는 어떻게 될까?
1 -> 2 -> 3 -> 0 -> 1 이 되어 결국 같은 경로를 나타내게 된다.
그렇다면 어떤 지점을 시작 지점으로 상관없다는 말이 된다.
그래서 나는 0번 지점을 시작 지점으로 하기로 했다.
🎯 비트마스크 사용 방법
먼저 마을의 상태를 나타내는 방법을 알아보자
0 ~ 3번 마을이 있다고 가정하자. 나는 이 마을의 번호를 2**k의 k라고 생각하기로 했다.
0번 마을의 경우 2**0 = 1
1번 마을의 경우 2**1 = 2
2번 마을의 경우 2**2 = 4
3번 마을의 경우 2**3 = 8
예를 들어 1010 의 경우 3번 마을과 1번 마을을 방문한 상태를 의미한다는 것이다.
🎯 DP 사용 방법
그렇다면 방문 순서는 어떻게 될까 ?
1010의 경우 시작지점인 0번에서 1번을 방문한 후에 3번을 방문한 상태일 수도 있고
시작지점인 0번에서 3번을 방문 후 1번을 방문한 상태일 수도 있다.
이렇듯 같은 1010이더라도 그전에 어떤 상태에서 왔는지에 따라 상태가 다르다
그러므로 이 부분을 DP table로 처리를 해주었다.
먼저 DP는 DP[상태][이전 마을] 형식으로 만들었다.
0 ~ 3번 마을이 있다고 가정하면
상태는 0000 ~ 1111까지 이므로 상태는 0 ~ 15까지 나올 수 있다. 즉 2**(노드의 수) 가 된다.
이전 마을의 경우 0 ~ 3이므로 마을의 개수가 된다.
🎯 탐색 방법 ( DFS )
그렇다면 0000 ~ 1111 까지 어떤 방법으로 탐색할까 ?
나는 0000부터 시작해 각 노드를 하나씩 방문하여 1111까지 한 번에 한 경로의 끝까지 탐색하는 DFS를 사용하기로 했다.
이때 현재의 상태 ( 1010 처럼 어떤 노드를 방문했는지에 대한 상태 )와 그 이전 노드에 대한 정보(1010 이면 가장 최근에 3번 노드를 방문했는지 1번 노드를 방문했는지 알 수 없으므로 )를 매개변수로 사용했다.
그렇다면 DFS는 어떤 값을 return 하는 것일까 ?
나는 return 값으로 현재 상태와 현재 노드에서 1111 상태로 가기 위한 최소 값을 리턴하도록 했다.
DFS 알고리즘은 다음과 같다.
방문하지 않은 노드를 탐색한다. ( 0번 노드는 제외한다. 마지막에 다시 시작 위치를 방문해야 하기 때문에 마지막으로 방문한다. )
이때 탐색 도중 DP에 저장된 값이 있는 경우 탐색을 멈추고 DP 값을 리턴하도록 했다.
🐳 실패코드 - (55% 에서 시간초과)
import sys
# f = open("practice.txt","r")
f = sys.stdin
INF = 10**9
N = int(f.readline().rstrip())
costs = [ list(map(int,f.readline().rstrip().split())) for _ in range(N) ]
# DP 를 INF로 초기화
dp = [[INF for _ in range(N)] for _ in range(1<<N)]
# DFS 에서 마지막 도착지점 1111 판별 코드를 지우기 위해 마지막 DP 값을 미리 넣어줌
# 111...0 상태에서 111...1로 가는 값을 dp에 미리 넣어줌
for i in range(1,N):
if costs[i][0]:
dp[(1<<N)-2][i] = costs[i][0]
else:
dp[(1<<N)-2][i] = INF - 1
def dfs(now,pre):
# DP 값이 INF가 아닌 경우 이미 방문했다는 소리이므로 DP 값을 return
if dp[now][pre] < INF:
return dp[now][pre]
# 0번 노드는 마지막에 방문해야 하므로 1~N까지 탐색
for i in range(1,N):
# 경로 값이 0 인 경우 경로가 없다는 얘기이므로 continue
if not costs[pre][i]:
continue
# 이미 방문한 경우 continue
if now & 1<<i:
continue
# dp값을 현재 dp값과 i번 노드를 방문했을 때의 경로의 최단거리와 비교해 저장
dp[now][pre] = min(dp[now][pre], dfs(now|1<<i,i) + costs[pre][i])
return dp[now][pre]
# 0번 노드에서 시작했을 때 111...1 로 가기 위한 경로의 최소값을 출력
print(dfs(0,0))
🐳 실패 원인 분석 - (55% 에서 시간초과)
이처럼 코드를 구성했을 때 계속 55%에서 계속 시간이 초과되었다.
잠깐 참혹한 그날의 현장을 보고 가자 무서운 건 다음 페이지에도 시간초과가 저만큼 있었다...
도대체 왜 시간초과가 발생하는 것일까 ?
답은 DP를 INF로 초기화하는 것에 있었다.
그렇다면 왜 INF로 초기화하면 시간초과가 발생하는 것일까 ?
DP를 INF로 초기화하고 DFS를 실행하면 발생할 수 있는 문제는
방문을 했는데 경로가 없어 INF가 DP에 저장되는 경우이다.
즉 DP값에 저장된 INF 값이 방문을 했는데 경로가 없어서 INF 인지 방문을 안 한 건지 알 수가 없어
방문한 경로임에도 불구하고 DP에 저장된 INF를 return하는 것이 아니라 계속 DFS를 수행한다는 것이다.
이는 반복된 연산을 줄이기 위해 사용하는 DP의 원리에 위배되는 것이다.
그래서 나는 DP 값을 -1로 초기화하기로 했다
🐳 성공 코드
import sys
f = sys.stdin
N = int(f.readline().rstrip())
costs = [ list(map(int,f.readline().rstrip().split())) for _ in range(N) ]
INF = 10**9
# DP를 -1로 초기화
dp = [[-1 for _ in range(N)] for _ in range(1<<N)]
# 마지막 DFS의 끝나는 지점 판별을 위한 if 문을 제거하기 위해 미리 최종경로 값 저장
# 0번 노드를 마지막에 방문해야 하므로 111...0 상태가 가장 마지막 상태이므로 (1<<N) - 2 가 된다.
for i in range(1,N):
if costs[i][0]:
dp[(1<<N)-2][i] = costs[i][0]
else:
dp[(1<<N)-2][i] = INF
def dfs(now,pre):
# 방문한 노드인 경우 DP 값을 리턴한다.
if dp[now][pre] != -1:
return dp[now][pre]
# 0번 노드는 마지막에 방문해야하므로 0번 노드를 재외하고 반복문을 수행한다.
for i in range(1,N):
# 경로가 없는 경우 지나감
if not costs[pre][i]:
continue
# 이미 방문한 경우 지나감
if now & 1<<i:
continue
# 처음 방문한 경우 min 을 사용할 수 없으므로 그냥 경로 값을 저장
if dp[now][pre] == -1:
dp[now][pre] = dfs(now|1<<i,i) + costs[pre][i]
# 이미 방문했던 경우 경로의 최단거리를 min을 사용해 저장
else:
dp[now][pre] = min(dp[now][pre], dfs(now|1<<i,i) + costs[pre][i])
# 모든 반복문을 수행한 후에 dp의 값이 -1인 경우
# 이 경우는 지금 상태 (now) 에서 1111..1(최종경로)로 가는 경우가 없다는 것을 의미한다.
# 그러므로 -1이 아닌 INF를 저장해 줌으로써 방문했지만 경로가 없다는 것을 나타내준다.
if dp[now][pre] == -1:
return INF
return dp[now][pre]
print(dfs(0,0))
위의 코드와 함께 주석을 잘 읽어보시기 바란다. 특히 마지막에 dp 값이 -1인 경우 INF 로 값을 저장해 주는 것이 중요하다.
이는 현재 상태에서 최종경로로 가는 경로가 없음을 나타내기 때문이다.
이 차이로 인해서 처음에 dp를 INF로 초기화했을 때와는 다르게 방문했지만 경로가 없는 경우를 표현해 줄 수 있다.
🐳 후기 ( 감동 주의 )
정말 이 문제 때문에 3일을 고민했다 ... 그만큼 해결했을 때의 기쁨은 참 짜릿했다.
그리고 질문게시판에 들어가 보니 나와 같은 어려움을 겪는 유저가 있길래 나의 풀이를 공유했다.
그랬는데 ... 이런 댓글을 받았다.
너무 행복했다 ... 내가 어렵게 푼 풀이를 다른 사람이 공감해 주고 기뻐한다는 게!!
이런 게 정말 나눔의 기쁨 아닐까?
역시 혼자 성장하는 것보다 함께 성장하는 것이 무엇보다 값어치 있는 일임을 다시 한번 깨닫게 된다.