[파이썬] 백준 9328 : 열쇠 (골드1)

[파이썬] 백준 9328 : 열쇠 (골드1)

9328번: 열쇠

---

문제

---

풀이

0. 방향성 생각

• BFS + 시뮬레이션
• BFS를 돌리면서 열쇠를 먹은 경우, 현재 상태를 변화시킨다.
• 변화된 상태에서 BFS를 또 돌리고 반복한다.
• 핵심은 열쇠를 먹고나서 BFS를 돌렸는데 변화가 없는 경우 탐색이 끝난 것.
• visit 배열을 어떻게 구성할까 하다가, 문제 조건에서 A to Z까지 다 나와서 26개를 비트마스킹으로 하기에는 array 크기가 좀 큰편이라 다른 방법 생각.
• 위에 생각처럼 한 stage마다 visit을 만들어서 BFS를 반복하는 식으로 구현.
• 이 문제의 엣지 케이스는 시작점을 어떻게 구성하냐이다. 이 설명은 입력 받으면서 시작.

1. 전역변수

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

shift = {chr(i+97):i for i in range(26)}
dire = [(1,0),(0,1),(-1,0),(0,-1)]

• 변환시킬거랑, 방향 이동은 전역으로

2. stage 구현

for _ in range(int(input())):
    h,w = map(int,input().split())
    arr= [list(input()) for _ in range(h)]

    stt = 0
    s = input()
    if s != '0':
        for key in s:
            stt = stt|(1<<shift[key])

    starts,doors = [],[]
    answer = set()
    for i in range(h):
        for j in range(w):
            a = arr[i][j]
            if (i==0 or i==h-1) or (j==0 or j==w-1):
                if a == '.':
                    starts.append((j,i))
                elif a == '$':
                    starts.append((j,i))
                    answer.add((j,i))
                elif a.islower():
                    starts.append((j,i))
                    stt = stt|(1<<shift[a])
                elif a.isupper():
                    doors.append((a,(j,i)))
    while True:
        nstt = bfs(stt)
        if stt == nstt:
            break
        stt = nstt
    print(len(answer))

• 일단 처음 상태 stt는 마지막 입력으로 주어진 string을 기반으로 열쇠 정보를 채워준다.
• 그 이후에 arr을 탐색하면서 외곽을 탐색한다. 풀고 보니까 range쓰지 말고 그냥 for문 튜플에 (0,h-1) 이런식으로 넣으면 될듯

 

• 탐색하면서 .은 바로 시작점으로 사용
• 돈인 경우에는 바로 정답개수를 카운트 해주면서 시작점으로 사용
• 열쇠인 경우에는 열쇠를 먹고 현재 상태를 업데이트 시키고 시작점으로 사용
• 문인 경우에는 열쇠가 있는 경우에만 시작점으로 사용 가능. 문의 경우에는 doors에 따로 넣는다.

 

• 이후 BFS를 돌리면서 상태변화가 있으면 BFS를 돌린다.
• 상태변화가 없으면 더이상 탐색할 수 없다는 이야기이므로 루프를 멈추고 훔친 돈의 개수를 카운트한다.

3. BFS 함수 정의

def bfs(state):

    q = deque(starts)
    for door,loc in doors:
        if state&(1<<shift[door.lower()]):
            q.append(loc)

    visit = [[False]*w for _ in range(h)]
    while q:
        x,y = q.popleft()
        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            if 0<=nx<w and 0<=ny<h:
                na = arr[ny][nx]
                if na == '.' and not visit[ny][nx]:
                    q.append((nx,ny))
                    visit[ny][nx] = True
                elif na.islower() and not visit[ny][nx]:
                    state = state|(1<<shift[na])
                    q.append((nx,ny))
                    visit[ny][nx] = True
                elif na.isupper() and not visit[ny][nx] and state&(1<<shift[na.lower()]):
                    q.append((nx,ny))
                    visit[ny][nx] = True
                elif na == '$' and not visit[ny][nx]:
                    q.append((nx,ny))
                    visit[ny][nx] = True
                    answer.add((nx,ny))
    return state

• 큐에 starts를 넣어준다.
• 열쇠가 있는 경우, 문을 따고 시작점으로 선택할 수 있으니 열쇠 유무를 확인하고 큐에 삽입
• 다른 부분은 일반적인 BFS랑 똑같다.
• 열쇠를 먹으면 state를 업데이트 시킨다.
• 문이면 열쇠가 있는 경우에 오픈가능

 

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

shift = {chr(i+97):i for i in range(26)}
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def bfs(state):

    q = deque(starts)
    for door,loc in doors:
        if state&(1<<shift[door.lower()]):
            q.append(loc)

    visit = [[False]*w for _ in range(h)]
    while q:
        x,y = q.popleft()
        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            if 0<=nx<w and 0<=ny<h:
                na = arr[ny][nx]
                if na == '.' and not visit[ny][nx]:
                    q.append((nx,ny))
                    visit[ny][nx] = True
                elif na.islower() and not visit[ny][nx]:
                    state = state|(1<<shift[na])
                    q.append((nx,ny))
                    visit[ny][nx] = True
                elif na.isupper() and not visit[ny][nx] and state&(1<<shift[na.lower()]):
                    q.append((nx,ny))
                    visit[ny][nx] = True
                elif na == '$' and not visit[ny][nx]:
                    q.append((nx,ny))
                    visit[ny][nx] = True
                    answer.add((nx,ny))
    return state

for _ in range(int(input())):
    h,w = map(int,input().split())
    arr= [list(input()) for _ in range(h)]

    stt = 0
    s = input()
    if s != '0':
        for key in s:
            stt = stt|(1<<shift[key])

    starts,doors = [],[]
    answer = set()
    for i in range(h):
        for j in range(w):
            a = arr[i][j]
            if (i==0 or i==h-1) or (j==0 or j==w-1):
                if a == '.':
                    starts.append((j,i))
                elif a == '$':
                    starts.append((j,i))
                    answer.add((j,i))
                elif a.islower():
                    starts.append((j,i))
                    stt = stt|(1<<shift[a])
                elif a.isupper():
                    doors.append((a,(j,i)))
    while True:
        nstt = bfs(stt)
        if stt == nstt:
            break
        stt = nstt
    print(len(answer))

 

코멘트

. / 열쇠 / 돈 / 문에서 시작가능한거 생각했으면 원트 가능인데 생각을 아예 못했음. ㅠ