이번 문제는 BFS를 통해 해결하였다. 큐에 a의 현재 좌표, b의 현재 좌표, 이동 횟수를 저장하고, 9가지의 방향을 각각 적용하여 주어진 조건이 모두 만족할 경우에 이동시키는 방식으로 구현하였다. 방문처리는 4차원 리스트를 사용하여 a와 b 둘의 위치를 모두 고려하도록 하였다. 문제를 보자마자 풀이방법이 생각났고, 그대로 구현하여 바로 해결되어 기분이 좋았다.

Code

from collections import deque
n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
ay, ax = 0, 0
by, bx = 0, 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == 'A':
            ay, ax = i, j
            grid[i][j] = '.'
        if grid[i][j] == 'B':
            by, bx = i, j
            grid[i][j] = '.'
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1, 0], [0, 1, 1, 1, 0, -1, -1, -1, 0]
def move_A_and_B():
    q = deque()
    q.append((ay, ax, by, bx, 0))
    visited = [[[[False for _ in range(m)] for _ in range(n)] for _ in range(m)] for _ in range(n)]
    visited[ay][ax][by][bx] = True
    while q:
        cay, cax, cby, cbx, cnt = q.popleft()
        if (cay, cax, cby, cbx) == (by, bx, ay, ax):
            return cnt
        for i in range(9):
            nay, nax = cay+dy[i], cax+dx[i]
            if not (0 <= nay < n and 0 <= nax < m and grid[nay][nax] == '.'):
                continue
            for j in range(9):
                nby, nbx = cby+dy[j], cbx+dx[j]
                if not (0 <= nby < n and 0 <= nbx < m and grid[nby][nbx] == '.'):
                    continue
                if ((nay, nax) == (cby, cbx)) and ((nby, nbx) == (cay, cax)):
                    continue
                if (nay, nax) == (nby, nbx):
                    continue
                if not visited[nay][nax][nby][nbx]:
                    visited[nay][nax][nby][nbx] = True
                    q.append((nay, nax, nby, nbx, cnt+1))
    return -1
print(move_A_and_B())