[BOJ] 2151 - 거울 설치 (Python)

 

 

아이디어

 

BFS로 방문하는 칸에 거울을 설치할 수 있는지에 따라 방향을 회전하며 설치해야 할 거울의 최소 개수를 구한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    N = int(input())
    board = [[*input().rstrip()] for _ in range(N)]
    doors = []
    for r in range(N):
        for c in range(N):
            if board[r][c] == '#':
                doors.append((r, c))
    stack = []
    for d in range(4):
        stack.append((*doors[0], d))
    cnt = 1
    while stack:
        _stack = []
        while stack:
            r, c, d = stack.pop()
            dr, dc = delta[d]
            nr, nc = r+dr, c+dc
            for k in range(N-1):
                if N > nr >= 0 and N > nc >= 0:
                    if board[nr][nc] == '!':
                        board[nr][nc] = '.'
                        _stack.append((nr, nc, (d+1)%4))
                        _stack.append((nr, nc, (d+3)%4))
                    elif board[nr][nc] == '#':
                        board[nr][nc] = '.'
                    elif board[nr][nc] == '*':
                        break
                else:
                    break
                nr += dr
                nc += dc
        if board[doors[1][0]][doors[1][1]] == '.':
            print(cnt-1)
            break
        stack = _stack
        cnt += 1

solution()