[백준 파이썬] 9328 열쇠

백준 9328

건물의 모든 외부에서 입구가 생길 수 있으므로 전체 외곽을 방문 가능한 곳으로 추가해준다.
열쇠를 발견했다면 잠겨있는 곳으로 다시 가야하므로 방문 기록을 초기화시켜준다.

from collections import deque, Counter

T = int(input())
for _ in range(T):

    h, w = map(int, input().split())
    # 건물 외부에 접근 가능하도록
    building =  [['.'] + list(input()) + ['.'] for _ in range(h)]
    building =  [['.']*(w+2)] + building + [['.']*(w+2)]
    key_cnt = Counter(input())
    keys = {}
    for char in range(ord('a'), ord('z')+1):
        if key_cnt[chr(char)] != 0: # 가지고 있는 키 저장
            keys[chr(char)] = True
        else:
            keys[chr(char)] = False


    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    def bfs():
        q = deque([[0, 0]])
        visited = [[False for _ in range(w+2)] for _ in range(h+2)]
        visited[0][0] = True
        count = 0

        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0 <= nx < w+2 and 0 <= ny < h+2
                	# 방문한적이 없고 벽이 아니라면
                    and building[ny][nx] != '*'
                    and not visited[ny][nx]):
					
                    # 방문한 위치가 열쇠가 있는 곳이라면
                    if 'a' <= building[ny][nx] <= 'z':
                    	# 열쇠가 없었을 경우
                        if not keys[building[ny][nx]]:
                        	# 열쇠 추가
                            keys[building[ny][nx]] = True
                            # 방문 기록 초기화
                            visited = [[False for _ in range(w+2)] for _ in range(h+2)]
                    
                    # 방문한 위치가 잠겨있다면
                    elif 'A' <= building[ny][nx] <= 'Z':
                    	# 해당 키가 없을 경우
                        if not keys[building[ny][nx].lower()]:
                            continue # 다음 위치로
                    
                    # 방문 위치에 문서가 있다면
                    elif building[ny][nx] == '$':
                    	# 카운트, 중복되지 않도록 빈 공간으로
                        count += 1
                        building[ny][nx] = '.'
					
                    # 방문한 위치 추가
                    visited[ny][nx] = True
                    q.append([nx, ny])

        return count

    print(bfs())