백준 6087 레이저 통신 (파이썬)

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

6087번: 레이저 통신

C 한 지점을 bfs에 입력하고 다른 지점에 도착할 때 까지의 최소 방향 전환 횟수를 구한다

 

1. 동남서북 순으로 방향에 대한 배열 dx, dy를 설정해준다

2. 방문했는지 체크할 배열을 3차원으로 해서 3차 변수를 바라보는 방향을 체크한다

3. 각 방향에 대한 초기값을 큐에 입력하고 방문한 것을 체크한다

4. bfs로 이동하면서 다음칸이 . 인데 방문하지 않았거나, 방문했으나 현재 칸보다 값이 크면 값을 갱신한다

5. 갱신 한 후 다음 칸에서 방향전환을 할 수 있는지 확인한다

   다음 방향을 turn 함수의 ndir 배열과 같이 설정하면 현재 바라보는 방향에 대한 90도 방향으로 바꿀 수 있다

6. 목적지에 도착하면 ans 배열에 저장해두고 모든 탐색을 마친 후 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):
    q.extend([[x, y, 0], [x, y, 1], [x, y, 2], [x, y, 3]])
    c[x][y] = [1, 1, 1, 1]
    ans = []
    while q:
        x, y, dir = q.popleft()
        nx = x + dx[dir]
        ny = y + dy[dir]
        if 0 <= nx < h and 0 <= ny < w:
            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]
                    q.appendleft([nx, ny, dir])
                    turn(nx, ny, dir)
                elif nx == x2 and ny == y2:
                    c[nx][ny][dir] = c[x][y][dir]
                    ans.append(c[nx][ny][dir])

    print(min(ans)-1)

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

w, h = map(int, input().split())

a, temp = [], []
for i in range(h):
    row = list(input().strip())
    a.append(row)
    for j, k in enumerate(row):
        if a[i][j] == 'C':
            temp.extend([i, j])
x1, y1, x2, y2 = temp

q = deque()
c = [[[0]*4 for _ in range(w)] for _ in range(h)]
bfs(x1, y1)