[Python] 20130번 Metroidvania Extreme

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

20130번: Metroidvania Extreme

---

 

22/10/08

 

 

독특한 아이디어가 돋보이는 BFS문제로, 일반적인 BFS가 아니라 더 재미있게 느껴졌던 문제이다.

---

 

문제 접근 방식:

 

 

일단 당연히 시작 지점부터 무지성으로 BFS를 진행하면 안 된다.

 

해당 알파벳의 대문자 지점은 해당 알파벳의 소문자가 열쇠인데, 그 열쇠를 얻어야만 대문자 지역을 지날 수 있다는 제약조건이 걸려있기 때문이다.

 

이 문제의 핵심 아이디어는, 대문자 지역을 방문했을 때 열쇠를 얻기 전의 상태라면, 방문처리를 하지 않은 상태로 다시 큐에 집어넣는다는 것이다.

 

이 아이디어를 생각하고 나니, 일반 BFS와 별 다른 점이 없어서 나머지는 그대로 BFS 하는 것처럼 구현했더니 맞았습니다를 받았다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 20310번 Metroidvania Extreme
# 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
matrix = [list(input().rstrip()) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
for row in range(N):
    for col in range(M):
        if matrix[row][col] == '#':
            visited[row][col] = 1

coordinates = []
locked = set(chr(i) for i in range(65, 91))
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def bfs(row, col):
    queue = deque()
    start = (row, col)
    queue.append(start)
    while queue:
        row, col = queue.popleft()
        if matrix[row][col] in locked:
            queue.append((row, col))
            continue
        else:
            coordinates.append((row+1, col+1))
            if matrix[row][col].islower():
                locked.discard(matrix[row][col].upper())
            if matrix[row][col] == '!':
                return
            else:
                for r, c in zip(dr, dc):
                    nr, nc = row + r, col + c
                    if 0 <= nr < N and 0 <= nc < M and visited[nr][nc] == 0:
                        visited[nr][nc] = 1
                        queue.append((nr, nc))

for row in range(N):
    for col in range(M):
        if matrix[row][col] == '@':
            visited[row][col] = 1
            bfs(row, col)
            break
print(len(coordinates))
for row, col in coordinates:
    print(row, col)