[백준 2098번] 외판원 순회 (비트마스킹) - Python / 시관초과 해결방법

🐳 문제 - [백준] 외판원 순회 (2098번)

---

백준 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일 만에 결국 성공

 

 

🐳 후기 ( 감동 주의 )

---

정말 이 문제 때문에 3일을 고민했다 ... 그만큼 해결했을 때의 기쁨은 참 짜릿했다.

그리고 질문게시판에 들어가 보니 나와 같은 어려움을 겪는 유저가 있길래 나의 풀이를 공유했다.

그랬는데 ... 이런 댓글을 받았다.

백준 질문 게시판의 선순환

너무 행복했다 ... 내가 어렵게 푼 풀이를 다른 사람이 공감해 주고 기뻐한다는 게!!

이런 게 정말 나눔의 기쁨 아닐까?

 

역시 혼자 성장하는 것보다 함께 성장하는 것이 무엇보다 값어치 있는 일임을 다시 한번 깨닫게 된다.