백준 2151 거울 설치 (파이썬)

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

2151번: 거울 설치

방문을 확인할 c 행렬을 3차원으로 해서 3번째 차수를 상하좌우에 대한 방문으로 사용

 

1. bfs에 입력할 문의 좌표에서 어느 방향으로 이동할 수 있는지 dir 변수에 저장한다

2. bfs로 다음칸에 방문하지 않았거나 현재 c 값보다 크다면 방문하여 갱신한다

3. 방문한 칸이 문이라면 ans에 저장하고 다음 반복문으로 넘어간다

4. 방문한 칸이 ! 라면 90도로 방향을 전환하고 c 값을 증가한다

5. bfs가 끝나면 ans 중 최소값을 출력

from collections import deque
import sys

input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs(x, y, dir):
    q.append([x, y, dir])
    c[x][y][dir] = 1
    ans = []
    while q:
        x, y, dir = q.popleft()
        nx = x + dx[dir]
        ny = y + dy[dir]
        if 0 <= nx < n and 0 <= ny < n:
            if not c[nx][ny][dir] or c[nx][ny][dir] > c[x][y][dir]:
                if a[nx][ny] != '*':
                    c[nx][ny][dir] = c[x][y][dir]
                    if nx == fx and ny == fy:
                        ans.append(c[nx][ny][dir])
                        continue
                    q.append([nx, ny, dir])
                    if a[nx][ny] == '!':
                        turn(nx, ny, dir)

    print(min(ans)-1)

def turn(x, y, dir):
    ndir = [(dir+1) % 4, (dir+3) % 4]
    for d in ndir:
        if not c[x][y][d] or c[x][y][d] > c[x][y][dir] + 1:
            c[x][y][d] = c[x][y][dir] + 1
            q.append([x, y, d])

n = int(input())
q = deque()
c = [[[0]*4 for _ in range(n)] for _ in range(n)]

a, temp = [], []
for i in range(n):
    row = list(input().strip())
    a.append(row)
    for j in range(n):
        if row[j] == '#':
            temp.extend([i, j])
sx, sy, fx, fy = temp

for i in range(4):
    nx = sx + dx[i]
    ny = sy + dy[i]
    if 0 <= nx < n and 0 <= ny < n:
        if a[nx][ny] != '*':
            dir = i
            break

bfs(sx, sy, dir)