[파이썬] 백준 1194: 달이 차오른다, 가자. (골드1)

[파이썬] 백준 1194: 달이 차오른다, 가자. (골드1)

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

---

문제

---

풀이

0. 방향성 생각

• 열쇠를 먹은 유무에 따라 문을 열수있는지 여부가 정해진다.
• 2D 배열이 2500, 열쇠가 6개이므로 2500*64 정도면 충분히 비트마스킹으로 가능
• 3D visit 배열을 만들어서 BFS로 진행

1. 입력

from collections import deque,defaultdict as dd
import sys

input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]
keys,doors = dd(int),dd(int)
for i in range(h):
    for j in range(w):
        val = arr[i][j]
        if val == '0':
            sx,sy = j,i
        elif val in ('a','b','c','d','e','f'):
            keys[val] += 1
        elif val in ('A','B','C','D','E','F'):
            doors[val] += 1

• 끝 지점이 여러개이므로 ends에 배열 저장해주기
• 키랑 문이 매칭이 안되는 케이스가 존재하니 각각 따로 세주기

2. 함수 정의

visit = [[[False]*w for _ in range(h)] for _ in range(1<<6)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]
shift = {chr(i+97):i for i in range(6)}

q = deque([(0,sx,sy,0)])
visit[0][sy][sx] = True
escape = -1
while q:
    t,x,y,s = q.popleft()
    
    for dx,dy in dire:
        nx,ny,nt = x+dx,y+dy,t+1
        if 0<=nx<w and 0<=ny<h:
            na = arr[ny][nx]
            if (na == '.' or na == '0') and not visit[s][ny][nx]:
                q.append((nt,nx,ny,s))
                visit[s][ny][nx] = True
            elif na in keys:
                ns = s|(1<<shift[na])
                if not visit[ns][ny][nx]:
                    q.append((nt,nx,ny,ns))
                    visit[ns][ny][nx] = True
            elif na in doors:
                if s&(1<<shift[na.lower()]) and not visit[s][ny][nx]:
                    q.append((nt,nx,ny,s))
                    visit[s][ny][nx] = True
            elif na == '1':
                escape = nt
                break
    if escape != -1:
        break

print(escape)

• 각 열쇠마다 번호를 부여해서 얼마나 shift하는지 정한다.
• 시작점이랑 이동가능한 방은 일반 BFS처럼 진행한다. 
• 열쇠를 먹으면 비트마스킹을 통해 상태를 ns로 업데이트 시킨다. 다음 상태의 node에 방문처리가 안돼있으면 큐에 추가.
• 문을 만났을 때, 현재 상태에서 비스마스킹을 통해 열쇠의 유무를 확인한다.
• 1을 만나면 탈출하기

---

전체코드

from collections import deque,defaultdict as dd
import sys

input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]
keys,doors = dd(int),dd(int)
for i in range(h):
    for j in range(w):
        val = arr[i][j]
        if val == '0':
            sx,sy = j,i
        elif val in ('a','b','c','d','e','f'):
            keys[val] += 1
        elif val in ('A','B','C','D','E','F'):
            doors[val] += 1

visit = [[[False]*w for _ in range(h)] for _ in range(1<<6)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]
shift = {chr(i+97):i for i in range(6)}

q = deque([(0,sx,sy,0)])
visit[0][sy][sx] = True
escape = -1
while q:
    t,x,y,s = q.popleft()
    
    for dx,dy in dire:
        nx,ny,nt = x+dx,y+dy,t+1
        if 0<=nx<w and 0<=ny<h:
            na = arr[ny][nx]
            if (na == '.' or na == '0') and not visit[s][ny][nx]:
                q.append((nt,nx,ny,s))
                visit[s][ny][nx] = True
            elif na in keys:
                ns = s|(1<<shift[na])
                if not visit[ns][ny][nx]:
                    q.append((nt,nx,ny,ns))
                    visit[ns][ny][nx] = True
            elif na in doors:
                if s&(1<<shift[na.lower()]) and not visit[s][ny][nx]:
                    q.append((nt,nx,ny,s))
                    visit[s][ny][nx] = True
            elif na == '1':
                escape = nt
                break
    if escape != -1:
        break

print(escape)

 

코멘트

            elif na in doors:
                if s&(1<<shift[na.lower()]) and not visit[s][ny][nx]:
                    q.append((nt,nx,ny,s))
                    visit[s][ny][nx] = True

이 부분에서 visit에 s대신에 ns써놔서 자꾸 더미큐가 쌓여서 시간초과...

복붙 금지.......