백준 9328 [열쇠] 파이썬

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

 

거의 다 왔으나, 코드 최적화를 못해서 아쉽게 놓쳤다.... 

 

#백준 9328 열쇠
import sys
from collections import deque
dr=[0,0,1,-1]
dc=[1,-1,0,0]

T=int(sys.stdin.readline().rstrip())
for _ in range(T):
    ans=0
    N,M=map(int,sys.stdin.readline().split())
    visited=[[0 for _ in range(M)] for _ in range(N)]
    maps=[]
    needed_key_points=deque()
    keys=[]
    q=deque()
    for i in range(N):
        s=list(map(str,sys.stdin.readline().rstrip()))
        maps.append(s)
        for j in range(M):
                if i==0 or i==N-1 or j==0 or j==M-1:
                    if s[j]=='.':
                        q.append((i,j))
                    elif s[j]=='$':
                        q.append((i,j))
                        ans+=1
                        maps[i][j]='.'
                    elif 'a'<=maps[i][j]<='z':
                        q.append((i,j))
                        keys.append(s[j])
                        maps[i][j]='.'
                    elif 'A'<=maps[i][j]<='Z':
                        needed_key_points.append((i,j,maps[i][j]))
    keys.extend(list(map(str,sys.stdin.readline().rstrip())))

    for i in range(len(needed_key_points)):
        if chr(ord(needed_key_points[i][2])+32) in keys:
            q.append((needed_key_points[i][0],needed_key_points[i][1]))
    needed_key_points=[need_key_point for need_key_point in needed_key_points if need_key_point[2] not in keys]

    while q:
        r,c=q.popleft()
        visited[r][c]=1
        for i in range(4):
            R=r+dr[i]
            C=c+dc[i]
            if 0<=R<N and 0<=C<M and visited[R][C]==0:
                if maps[R][C]=='.':
                    q.append((R,C))
                elif maps[R][C]=='$':
                    ans+=1
                    q.append((R,C))
                    maps[R][C]='.'
                elif maps[R][C] in keys:
                    q.append((R,C))
                    maps[R][C]='.'
                elif 'a' <= maps[R][C] <='z':
                    q.append((R,C))
                    keys.append(maps[R][C])
                    new_key=chr(ord(maps[R][C])-32)
                    find_point=[]
                    for i in range(len(needed_key_points)):
                        if new_key==needed_key_points[i][2]:
                            q.append((needed_key_points[i][0],needed_key_points[i][1]))
                            find_point.append(needed_key_points[i][2])
                    needed_key_points=[need_key_point for need_key_point in needed_key_points if need_key_point[2] not in find_point]
                    maps[R][C]='.'
                elif 'A' <= maps[R][C] <='Z':
                    if chr(ord(maps[R][C])+32) in keys:
                        q.append((R,C))
                        maps[R][C]='.'
                    else:
                        needed_key_points.append((R,C,maps[R][C]))
    print(ans)

 

 

CHAT GPT의 코드를 첨부한다.

import sys
from collections import deque, defaultdict

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

T = int(sys.stdin.readline().rstrip())
for _ in range(T):
    ans = 0
    N, M = map(int, sys.stdin.readline().split())
    visited = [[0] * M for _ in range(N)]
    maps = []
    needed_key_points = defaultdict(list)
    keys = set()
    q = deque()

    for i in range(N):
        row = list(sys.stdin.readline().rstrip())
        maps.append(row)
        for j in range(M):
            if i == 0 or i == N - 1 or j == 0 or j == M - 1:
                if row[j] == '.':
                    q.append((i, j))
                    visited[i][j] = 1
                elif row[j] == '$':
                    q.append((i, j))
                    visited[i][j] = 1
                    ans += 1
                    maps[i][j] = '.'
                elif 'a' <= row[j] <= 'z':
                    q.append((i, j))
                    visited[i][j] = 1
                    keys.add(row[j])
                    maps[i][j] = '.'
                elif 'A' <= row[j] <= 'Z':
                    needed_key_points[row[j]].append((i, j))

    for key in sys.stdin.readline().rstrip():
        if key != '0':
            keys.add(key)

    for key in list(keys):  # 이미 있는 키로 문 열기
        if key.upper() in needed_key_points:
            for r, c in needed_key_points[key.upper()]:
                q.append((r, c))
                visited[r][c] = 1
            del needed_key_points[key.upper()]

    while q:
        r, c = q.popleft()

        for i in range(4):
            R, C = r + dr[i], c + dc[i]
            if 0 <= R < N and 0 <= C < M and not visited[R][C]:
                visited[R][C] = 1  # 방문 체크를 미리 수행

                if maps[R][C] == '.':
                    q.append((R, C))
                elif maps[R][C] == '$':
                    ans += 1
                    q.append((R, C))
                    maps[R][C] = '.'
                elif 'a' <= maps[R][C] <= 'z':
                    q.append((R, C))
                    keys.add(maps[R][C])
                    new_key = maps[R][C].upper()
                    if new_key in needed_key_points:
                        for x, y in needed_key_points[new_key]:
                            q.append((x, y))
                        del needed_key_points[new_key]
                    maps[R][C] = '.'
                elif 'A' <= maps[R][C] <= 'Z':
                    if maps[R][C].lower() in keys:
                        q.append((R, C))
                        maps[R][C] = '.'
                    else:
                        needed_key_points[maps[R][C]].append((R, C))

    print(ans)

 

 

딕셔너리와 set을 이용하는것이 중요했다.