[Python] 백준 1194번: 달이 차오른다, 가자.

https://www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

1. 각키마다 배열로 설정해주어 키를 가지고있을때와 그렇지않을때를 구분해두었다.

2. 다음 가는곳이 가능한곳인지 isPossible함수로 판별해주었다.

from collections import deque
input = sys.stdin.readline

dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
q = deque()
n, m = map(int, input().split())
field = [list(input().strip()) for _ in range(n)]
ch = [[[[[[[[0 for _ in range(2)]for _ in range(2)]for _ in range(2)]for _ in range(
    2)]for _ in range(2)] for _ in range(2)] for _ in range(m)] for _ in range(n)]

def isPossible(x, key):
    if x == '.' or x == '1':
        return [nx, ny, dis+1] + key
    if x in ['a', 'b', 'c', 'd', 'e', 'f']:
        key[ord(x) - 97] = 1
        return [nx, ny, dis+1] + key
    if x in ['A', 'B', 'C', 'D', 'E', 'F'] and key[ord(x) - 65]:
        return [nx, ny, dis+1] + key
    else:
        return False

for i in range(n):
    for j in range(m):
        if field[i][j] == '0':
            q.append((i, j, 0, 0, 0, 0, 0, 0, 0))
            field[i][j] = '.'
            break

while q:
    x, y, dis, a, b, c, d, e, f = q.popleft()
    if field[x][y] == '1':
        print(dis)
        sys.exit(0)
    if ch[x][y][a][b][c][d][e][f]:
        continue
    ch[x][y][a][b][c][d][e][f] = 1
    for k in range(4):
        nx, ny = x+dx[k], y+dy[k]
        if 0 <= nx < n and 0 <= ny < m:
            next = isPossible(field[nx][ny], [a, b, c, d, e, f])
            if(next):
                q.append(next)

print(-1)