[백준 9328번] 열쇠(파이썬)

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

9328번: 열쇠

 

처음 문제를 마주하고 조금 까다롭다고 생각한 문제.

그래도 일반적인 bfs라 생각하고 문제를 풀이했습니다.

#백준 9328 열쇠
from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]

T=int(input())



def bfs(sx,sy):
    global answer
    global key
    global visited
    q=deque()
    q.append((sx,sy))
    visited[sx][sy]=True
    mon=set()
    while q:
        x,y=q.popleft()
        if room[x][y]=='$':
            answer+=1
            mon.add((x,y))

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=h or ny<0 or ny>=w:
                continue

            if room[nx][ny]=='*':
                continue
            #빈공간
            if (room[nx][ny]=='.' or room[nx][ny]=='$') and not visited[nx][ny]:
                visited[nx][ny]=True
                q.append((nx,ny))
            #열쇠
            if 'a'<=room[nx][ny]<='z' and not visited[nx][ny]:
                key.append(room[nx][ny])
                #열쇠를 찾으면 이전에 못가던 곳도 지나가니깐 초기화를 해줬는데
                #아마 이 부분에서 시간초과가 난 것 같다
                visited=[[False]*w for _ in range(h)]
                mon.add((nx,ny))
                for vx,vy in mon:
                    visited[vx][vy]=True
                q.append((nx,ny))


            if 'A'<=room[nx][ny]<='Z' and not visited[nx][ny]:
                nkey=chr(ord(room[nx][ny])+32)
                if nkey in key:
                    q.append((nx,ny))



for _ in range(T):
    h,w=map(int,input().split())
    room=[list(input().rstrip()) for _ in range(h)]
    key=list(input().rstrip())
    visited=[[False]*w for _ in range(h)]
    answer=0
    #들어갈 구멍을 찾아본다
    for x in range(h):
        if x==0 or x==h-1:
            for y in range(w):
                if room[x][y]=='.' and not visited[x][y]:
                    bfs(x,y)
        else:
            for y in [0,w-1]:
                if room[x][y]=='.' and not visited[x][y]:
                    bfs(x,y)
    print(answer)

처음에 제출했던 코드.

주석에도 적혀있듯이

이 코드는 시간초과가 발생합니다.

이유는 열쇠를 찾고 나서인데요.

저는 열쇠를 찾는 경우에는

모든 길을 전부 초기화했습니다.

이전에는 열쇠가 없어서 못지나가는 문을

이제는 지나갈 수 있기 때문에,

갈 수 있는 곳이 달라져서

모든 방문기록을 초기화했습니다.

하지만 이 방식은 탐색시간이 너무 오래 걸려

시간초과를 야기했습니다.

 

구글링해서 힌트를 얻어서 다음과 같이 수정했습니다.

 

1. 배열의 크기를 더 늘린다

-->방을 들낙할 수 있기 때문에

행과 열을 +2씩 늘린다

 

2. 지나가지 못하는 문은

deque에다가 미리 받아둔다

-->이후 해당 문의 열쇠를 얻는다면

그 지역을 q에 넣어주고 탐색시작.

#백준 9328 열쇠
from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]


def bfs():
    q=deque()
    q.append((0,0))
    door=[deque() for _ in range(26)]
    visited=[[False]*(w+2) for _ in range(h+2)]
    visited[0][0]=True
    cnt=0
    while q:
        x,y=q.popleft()
        if room[x][y]=='$':
            cnt+=1

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=h+2 or ny<0 or ny>=w+2:
                continue

            if room[nx][ny]=='*':
                continue
            #빈공간 or 문서
            if (room[nx][ny]=='.' or room[nx][ny]=='$') and not visited[nx][ny]:
                visited[nx][ny]=True
                q.append((nx,ny))

            #문
            if 'A'<=room[nx][ny]<='Z' and not visited[nx][ny]:
                nkey=ord(room[nx][ny])-65
                visited[nx][ny]=True
                #아직 열쇠가 없다면 못들어감
                if keys[nkey]==False:
                    door[nkey].append((nx,ny))
                else:
                    q.append((nx,ny))
            #열쇠
            if 'a'<=room[nx][ny]<='z' and not visited[nx][ny]:
                visited[nx][ny]=True
                q.append((nx,ny))
                getkey=ord(room[nx][ny])-97
                keys[getkey]=True
                #이전에 못들어간게 있다면 추가해줌
                while door[getkey]:
                    px,py=door[getkey].popleft()
                    q.append((px,py))



    return cnt
T=int(input())
for _ in range(T):
    h,w=map(int,input().split())
    room=[]
    room.append(['.']*(w+2))
    for _ in range(h):
        tmp=input().rstrip()
        t='.'+tmp+'.'
        t=list(t)
        room.append(t)
    room.append(['.'] * (w + 2))
    k=list(input().rstrip())
    keys=[False]*26
    for key in k:
        if key=='0':
            continue
        ke=ord(key)-97
        keys[ke]=True
    print(bfs())

 

bfs문제중에서 까다로운 편에 속합니다.

방문한 지역을 또 방문가능하다는 가정이 있을때

어떻게 시간초과를 해결하면서

구현할 수 있을지 고민하게 만들어준 좋은 문제입니다.