백준 1938 통나무 옮기기

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

문제가 좀 길지만 읽다보면 문제 상황은 어느정도 심플하다.

BBB를 EEE로 맞추면 된다.

일단 통나무가 있을 수 있는 상태는 | 모양이거나 ㅡ 모양이다.
즉 가운데 위치와 어느 방향으로 서있는지만 알면 통나무의 위치와 모양이 트래킹 가능하다.
0,0 부터 n-1,n-1까지 오른쪽 아래방향으로 읽으면 어느 모양이건 항상 두번 째 나오는 문자가 중심점이다.
가장 최단경로를 구해야하니 bfs를 사용하였고,

중심점을 기준으로 bfs를 통해 EEE의 중심점으로 찾아가면 된다.

from collections import deque
n = int(input())
arr = []
for i in range(n):
    arr.append(list(input()))
b = []
e = []
for i in range(n):
    for j in range(n):
        if arr[i][j] =='B':
            b.append((i,j))
            arr[i][j] = '0'
        if arr[i][j] == 'E':
            e.append((i,j))
            arr[i][j] = '0'
def get_status(array):
    if array[0][0] == array[1][0]:
        d = 0 ## 누워있으면
    else:
        d = 1
    x = array[1][0]; y = array[1][1]
    return [x,y,d]
sx,sy,sd = get_status(b)
ex,ey,ed = get_status(e)
visited = [[[-1]*2 for i in range(n)] for i in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def check(x,y,d):
    for i in [-1,0,1]:
        if d == 1:
            nx = x + i
            ny = y
        elif d == 0:
            nx = x
            ny = y + i
        if nx < 0 or nx >= n or ny < 0 or ny >= n or arr[nx][ny] == '1':
            return False
    return True

def bfs():
    q = deque([])
    q.append((sx,sy,sd))
    visited[sx][sy][sd] = 0
    while q:
        x,y,d = q.popleft()
        if x == ex and y == ey and d == ed:
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny][d] != -1 or arr[nx][ny] == '1':
                continue
            if check(nx,ny,d):
                visited[nx][ny][d] = visited[x][y][d] + 1
                q.append((nx,ny,d))
        if visited[x][y][d^1] == -1:
            p = 1
            for i in [-1,0,1]:
                for j in [-1,0,1]:
                    nx = x + i
                    ny = y + j
                    if nx < 0 or nx >= n or ny < 0 or ny >= n or arr[nx][ny] == '1':
                        p = 0
            if p:
                visited[x][y][d^1] = visited[x][y][d] + 1
                q.append((x,y,d^1))

bfs()
ans = visited[ex][ey][ed]
if ans == -1:
    print(0)
else:
    print(ans)