[백준(BOJ)] #9328- 열쇠 (파이썬, PyPy3)

문제

 

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

9328번: 열쇠

 

---

문제 풀이

구현 문제로 BFS 알고리즘을 사용하여 문서의 최대 개수를 구할 수 있습니다.

2022.07.14 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

[파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

 

bfs 알고리즘을 적용하기 앞서 어떻게 빈 공간을 찾아서 그 위치에서 bfs 알고리즘을 적용할 수 있을지 고민을 해봤는데 빌딩 외곽에 빈 공간을 임의로 추가하여 이 부분을 해결할 수 있었습니다.

 

예를 들어 위와 같이 5(=W) X 5(=H) 빌딩 평면도가 있다고 가정하면

 

위와 같이 외곽에 빈 공간을 추가하여 7(=W+2) X 7(=H+2) 크기의 평면도로 만들어 준다음 어디로든 접근할 수 있게끔 하는 것입니다.

 

다음으로는 현재 가지고 있는 열쇠(알파벳 소문자)로 열 수 있는 문을 모두 열어 빈 공간(.)으로 만들어줍니다. 

 

그 후 bfs 알고리즘으로 상하좌우 네 방향으로 탐색을 합니다.

1) 다음 포지션이 히스토리에 없고 열쇠(알파벳 소문자)가 있는 포지션이면 지금까지 방문했던 히스토리를 다시 초기화하고 큐에 삽입 및 히스토리 추가

2) 다음 포지션이 히스토리에 없고 문(알파벳 대문자)이 위치한 포지션이면 해당 문을 열 수 있는 열쇠가 있을 때만 열쇠를 사용해 빈 공간(.)으로 만들고 큐에 삽입 및 히스토리 추가

3) 다음 포지션이 히스토리에 없고 그 포지션에 문서($)가 있으면 문서의 개수를 증가시키고 큐에 삽입 및 히스토리 추가

4) 다음 포지션이 히스토리에 없고 빈 공간(.)이면 큐에 삽입 및 히스토리 추가

5) 큐가 빌때까지 위 작업 반복

 

---

구현

코드

import sys
from collections import deque
input = sys.stdin.readline

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

# 해당 열쇠로 열 수 있는 문 표시
def init_doors():
    for key in keys:
        if key == '0':
            break
        doors[ord(key) - 97] = True
        
# 열 수 있는 문을 빈 공간으로 변경
def init_building():
    for i in range(1, h+1):
        for j in range(1, w+1):
            if building[i][j].isupper() and doors[ord(building[i][j].lower())-97]:
                building[i][j] = '.'
                
def bfs():
    res = 0
    check_building = [[False] * w for _ in range(h)]
    dq = deque()
    dq.append((0, 0))
    check_building[0][0] = True
    
    while dq:
        ti, tj = dq.popleft()
        for k in range(4):
            x = ti + dx[k]
            y = tj + dy[k]
            
            if 0 <= x < h and 0 <= y < w and building[x][y] != '*' and not check_building[x][y]:
                # 다음 포지션이 빈 공간이면 히스토리 추가 및 큐에 삽입
                if building[x][y] == '.':
                    check_building[x][y] = True
                    dq.append((x, y))
                else:
                    # 다음 포지션에 문서가 있으면 res 증가
                    if building[x][y] == '$':
                        res += 1
                        check_building[x][y] = True
                        dq.append((x, y))
                        building[x][y] = '.'
                    else:
                        # 다음 포지션에 문이 있으면 열 수 있으면 빈 공간으로 만들고 큐에 삽입
                        if building[x][y].isupper():
                            if doors[ord(building[x][y].lower())-97]:
                                building[x][y] = '.'
                                check_building[x][y] = True
                                dq.append((x, y))
                        # 다음 포지션에 열쇠가 있으면 히스토리 초기화
                        elif building[x][y].islower():
                            doors[ord(building[x][y].lower())-97] = True
                            building[x][y] = '.'
                            check_building = [[False] * w for _ in range(h)]
                            dq = deque()
                            dq.append((x, y))
    return res

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        h, w = map(int, input().split())
        building = list()
        # 외곽에 빈 공간 추가
        building.append(['.'] * (w + 2))
        for _ in range(h):
            building.append(['.'] + list(input().rstrip()) + ['.'])
        building.append(['.'] * (w + 2))
        
        keys = list(input().rstrip())
        doors = [False] * 26
        init_doors()
        init_building()
        
        h, w = h+2, w+2
                             
        print(bfs())

결과