[BOJ] 달이 차오른다 가자 in Python

문제 풀러 가기!

문제의 조건을 준수하면서 그래도 코드에 입히면 끝나는 문제였으나, 그게 쉬웠으면 Gold1에 랭크되어 있진 않겠지요..

요점은 문제의 조건을 어떻게 코드에 입힐 것인가? 입니다.
이때는 비트 마스크를 활용합니다.

비트마스크를 사용한 다는 것은 결국 어떤 상태를 기록하겠다는 의미거든요.

문제에는 어떤 상태가 존재할까요?

바로 민식이가 바로 어떤 키를 갖고 있는가? 입니다.

민식이가 갖고 있는 키값에 따라 갈 수 있는 경로가 달라지기 때문에 어떤 키를 갖고 있는지 여부를 bit로 구분하면 됩니다.

예를 들어서 문제에서 등장한 6개 키인 a~f를 1~6으로 대칭시켜보죠.

각각에 해당되는 key를 갖고 있다고 가정하면 다음과 같습니다.

f = 6	e = 5	d = 4	c = 3	b = 2	a = 1
100000	010000	001000	000100	000010	000001

이걸 6개의 모든 비트(2의 6제곱)에 대해 모든 방문 배열을 만듭니다. 이 방문 배열로 탐색할겁니다.

그리고 위의 근거로 인해 방문 배열은 3차원입니다.

1차원 → 갖고 있는 키 (state)
2차원 → 행
3차원 → 열

그러면 이제 이걸 코드로 반영해주어야되기 때문에 다음과 같은 코드로 미리 세팅해줍시다.

get_key = {
    "a": 0,
    "b": 1,
    "c": 2,
    "d": 3,
    "e": 4,
    "f": 5
}

use_key = {
    "A": 0,
    "B": 1,
    "C": 2,
    "D": 3,
    "E": 4,
    "F": 5
}

key = ["a", "b", "c", "d", "e", "f"]
set_key = set()
set_use_key = set()


for k in key:
    set_key.add(k)
    set_use_key.add(k.upper())

미로를 순회하다가 키값을 얻으면 바로 접근할 수 있도록 하기 위해서 get_key로 그리고 key를 사용할때는 대문자이기 때문에 use_key로 해당 dictionary를 사전에 세팅해주었습니다.

또한 6개의 key를 배열로 두지 않고 set으로 만들었습니다. 시간복잡도를 최대한 줄이기 위해서입니다. set으로 하면 제가 알기로 시간복잡도를 더 줄일 수 있는 것으로 알고 있습니다. 왜요? 라고 말씀하신다면.. 그냥 제가 문제를 풀어보면서 set으로 했을 때 시간 복잡도가 많이 줄어든 경험이 있어서 그런거 같습니다. 사실 여기서 더 설명하면 참조 지역성을 설명해야 되는데, 저 set은 아마 cpu에서 참조 지역성이 좁은 곳에 저장하지 않을까 생각드네요.

여튼 이제 키값을 갖는 state에 따라서 방문 여부를 체크할 visited 배열을 만들어줍시다.

# 델타이동
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

# 데이터 받기
n, m = map(int, input().split())
maze = [list(input().strip()) for _ in range(n)]

# 시작점 찾기
sx, sy = -1, -1
for i in range(n):
    for j in range(m):
        if maze[i][j] == "0":
            sx, sy = i, j
            break
    if sx != -1 and sy != -1:
        break

# 방문 배열 만들기
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range((1 << 6) + 1)]

그리고 탐색을 시도합시다

def find_exit(state, x, y, cnt):

    answer = int(10e9)
    q = deque([])
    q.append((state, x, y, cnt))
    
    while q:
    
        state, x, y, cnt = q.popleft()
        
        # 여기서 문제의 답을 도출할 것임
        if maze[x][y] == "1":
            answer = min(answer, cnt)

        for i in range(4):
        	# 다음 좌표
            nx, ny = x + dx[i], y + dy[i]
            
            # 범위에 벗어나거나 이미 해당 상태에서 방문 또는 벽이면 볼 필요없음
            if not (0 <= nx < n and 0 <= ny < m): continue
            if visited[state][nx][ny] or maze[nx][ny] == "#": continue
			
            # 민식이가 갈 수 있는 좌표임 열쇠를 얻은 것은 아니기 때문에 state가 바뀌지는 않음
            if (maze[nx][ny] == "." or maze[nx][ny] == "0" or maze[nx][ny] == "1") and not visited[state][nx][ny]:
                visited[state][nx][ny] = True
                q.append((state, nx, ny, cnt+1))

			# 민식이가 key를 얻었으므로 state를 변경해주어 q에 넣어줌
            elif maze[nx][ny] in set_key and not visited[state | (1 << get_key[maze[nx][ny]])][nx][ny]:
                visited[state | (1 << get_key[maze[nx][ny]])][nx][ny] = True
                q.append((state | (1 << get_key[maze[nx][ny]]), nx, ny, cnt+1))

			# 민식이가 갖고 있는 키의 상태로 갈 수 있음 주의할 것은 key의 상태는 바뀌지 않음. 만약에 키가 한 번쓰고 끝나는 문제라면 해당 부분을 0으로 바꿔주면 됨. 어떻게? xor 연산으로..
            elif maze[nx][ny] in set_use_key and state & (1 << use_key[maze[nx][ny]]):
                visited[state][nx][ny] = True
                q.append((state, nx, ny, cnt+1))
    
    return answer

ans = find_exit(0, sx, sy, 0)

처음에는 아무런 key도 갖고 있지 않기 때문에 state는 0입니다.
cnt는 이동한 경로를 세어줄겁니다.

이제 답을 도출합니다.

if ans == int(10e9):
    print(-1)
else:
    print(ans)

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

get_key = {
    "a": 0,
    "b": 1,
    "c": 2,
    "d": 3,
    "e": 4,
    "f": 5
}

use_key = {
    "A": 0,
    "B": 1,
    "C": 2,
    "D": 3,
    "E": 4,
    "F": 5
}

key = ["a", "b", "c", "d", "e", "f"]
set_key = set()
set_use_key = set()


for k in key:
    set_key.add(k)
    set_use_key.add(k.upper())

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

n, m = map(int, input().split())
maze = [list(input().strip()) for _ in range(n)]

sx, sy = -1, -1
for i in range(n):
    for j in range(m):
        if maze[i][j] == "0":
            sx, sy = i, j
            break
    if sx != -1 and sy != -1:
        break

visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range((1 << 6) + 1)]


def find_exit(state, x, y, cnt):
    answer = int(10e9)
    q = deque([])

    q.append((state, x, y, cnt))
    while q:
        state, x, y, cnt = q.popleft()
        if maze[x][y] == "1":
            answer = min(answer, cnt)

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if not (0 <= nx < n and 0 <= ny < m): continue
            if visited[state][nx][ny] or maze[nx][ny] == "#": continue

            if (maze[nx][ny] == "." or maze[nx][ny] == "0" or maze[nx][ny] == "1") and not visited[state][nx][ny]:
                visited[state][nx][ny] = True
                q.append((state, nx, ny, cnt+1))

            elif maze[nx][ny] in set_key and not visited[state | (1 << get_key[maze[nx][ny]])][nx][ny]:
                visited[state | (1 << get_key[maze[nx][ny]])][nx][ny] = True
                q.append((state | (1 << get_key[maze[nx][ny]]), nx, ny, cnt+1))

            elif maze[nx][ny] in set_use_key and state & (1 << use_key[maze[nx][ny]]):
                visited[state][nx][ny] = True
                q.append((state, nx, ny, cnt+1))
    
    return answer

ans = find_exit(0, sx, sy, 0)

if ans == int(10e9):
    print(-1)
else:
    print(ans)