이번 문제는 BFS를 통해 해결하였다. 이 문제에서의 키포인트는 통나무가 세로로 있을 수도 있고, 가로로 있을 수도 있다는 점과 목적지 또한 세로로, 혹은 가로로 있을 수 있다는 점이었다. 길이가 3으로 고정되어 있었기 때문에 3개의 좌표를 모두 관리할지, 중심 좌표와 방향으로 관리할지 고민하다가 중심 좌표와 방향으로 관리하기 하였다.

우선 입력받은 grid를 순회하며 통나무와 목적지의 각각 3개의 좌표를 tree, dest에 담고, tree와 dest를 확인하여 만약 y좌표끼리 같다면 가로모양 (0)으로, x좌표끼리 같다면 세로모양 (1)로 저장해주었다.

dy, dx를 통해 4가지 방향을 탐색할 수 있도록 하였고, 통나무를 회전시킬 때 가운데 좌표를 중심으로 주변 8개의 좌표를 확인해야 하므로, 이를 함수로 구현하였다. 그리고 4가지 방향으로 이동할 때, 이동하고자 하는 좌표를 확인하는 함수를 구현하여 방향이 세로일 때와 가로일 때를 나눠 확인할 수 있도록 하였다.

중심 좌표와 방향으로 저장을 하니, 통나무의 회전이 매우 간단해졌다. 가로를 0, 세로를 1로 저장했기 때문에 type을 1-type으로 갱신해주면 통나무의 회전이 구현되었다. 물론 이 과정 전에 8개의 좌표를 확인하는 함수를 통해 확인을 먼저 해주어야 한다.

큐에서 방금 꺼낸 데이터가 dest와 같을 경우 그 때에 해당하는 time을 반환하고, while문이 종료될 때까지 반환되지 못했다면 0을 반환하도록 하여 해결하였다.

Code

from collections import deque
n = int(input())
grid = [list(str(input())) for _ in range(n)]
tree = []
dest = []
for i in range(n):
    for j in range(n):
        if grid[i][j] == 'B':
            tree.append((i, j))
            grid[i][j] = '0'
        if grid[i][j] == 'E':
            dest.append((i, j))
if tree[0][0] == tree[1][0] == tree[2][0]: # 가로 모양
    tree = [tree[1], 0]
else: # 세로 모양
    tree = [tree[1], 1]
if dest[0][0] == dest[1][0] == dest[2][0]:
    dest = [dest[1], 0]
else:
    dest = [dest[1], 1]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def chk_square(y, x):
    sdy, sdx = [-1, -1, -1, 0, 1, 1, 1, 0], [-1, 0, 1, 1, 1, 0, -1, -1]
    for i in range(8):
        ny, nx = y+sdy[i], x+sdx[i]
        if 0 <= ny < n and 0 <= nx < n:
            if grid[ny][nx] == '1':
                return False
        else:
            return False
    return True
def chk_nxt_tree(y, x, type):
    if type == 0:
        if 0 <= y < n and 0 <= x-1 < n and 0 <= x < n and 0 <= x+1 < n and grid[y][x] != '1' and grid[y][x-1] != '1' and grid[y][x+1] != '1':
            return True
        return False
    elif type == 1:
        if 0 <= y-1 < n and 0 <= y < n and 0 <= y+1 < n and 0 <= x < n and grid[y-1][x] != '1' and grid[y][x] != '1' and grid[y+1][x] != '1':
            return True
        return False
def bfs():
    q = deque()
    q.append((tree[0][0], tree[0][1], tree[1], 0))
    visited = [[[False for _ in range(2)] for _ in range(n)] for _ in range(n)]
    visited[tree[0][0]][tree[0][1]][tree[1]] = True
    while q:
        y, x, type, time = q.popleft()
        if [(y, x), type] == dest:
            return time
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if chk_nxt_tree(ny, nx, type) and not visited[ny][nx][type]:
                visited[ny][nx][type] = True
                q.append((ny, nx, type, time+1))
        if chk_square(y, x) and not visited[y][x][1-type]:
            visited[y][x][1-type] = True
            q.append((y, x, 1-type, time+1))
    return 0
print(bfs())