백준 알고리즘 2151번 거울 설치 풀이 With Python

문제 링크:  https://www.acmicpc.net/problem/2151

2151번: 거울 설치

이 문제는 맨 처음 문인 '#'의 위치를 먼저 알아야 합니다. 따라서 문제에서 주어진 입력값을 통해 #의 좌표를 알아야 하고, 이후에 #의 4방향으로 집을 탐색해야 합니다. 그리고 방문할 좌표와 방향을 큐에 넣어야 하는데, 이때 큐에 넣고 꺼내어 탐색을 할 때 만약 해당 좌표와 방향으로 탐색한 적이 없거나 전에 탐색할 때보다 거울 설치 횟수가 적다면, 해당 좌표와 방향의 위치에 거울 설치 회수를 경신합니다. 저는 이것을 파이썬 자료구조인 dict로 해결하였습니다. 소스코드는 아래와 같습니다. 

 

import sys
from collections import deque

answer = float('inf')
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
n = int(sys.stdin.readline())
board = []
door = []
for i in range(n):
    s = sys.stdin.readline().rstrip()
    for j in range(n):
        if s[j] == '#':
            door.append((i, j))
    board.append(s)
queue = deque()
x, y = door[0]
visit = {}
tx, ty = door[1]
for d in range(4):
    visit[(x, y, d)] = 1
    nx = x + dx[d]
    ny = y + dy[d]
    if -1 < nx < n and -1 < ny < n:
        queue.append((nx, ny, 0, d))
while queue:
    x, y, count, d = queue.popleft()
    if -1 < x < n and -1 < y < n:
        if visit.get((x, y, d)) is None or visit[(x, y, d)] > count:
            visit[(x, y, d)] = count
            if x == tx and y == ty:
                answer = min(count, answer)
            elif board[x][y] == '!':
                queue.append((x + dx[d], y + dy[d], count, d))
                queue.append((x + dx[(d - 1) % 4], y + dy[(d - 1) % 4], count + 1, (d - 1) % 4))
                queue.append((x + dx[(d + 1) % 4], y + dy[(d + 1) % 4], count + 1, (d + 1) % 4))
            elif board[x][y] == '.':
                queue.append((x + dx[d], y + dy[d], count, d))
print(answer)

 

소스코드에 대한 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다.