이번 문제는 백트레킹과 BFS를 고민하다가 BFS로 풀이하였다. 동전이 2개로 고정되어 있으므로 2개의 동전의 좌표와 카운팅 변수를 deque에 넣어주고, 4개의 방향 리스트를 이용하여 모든 경우를 탐색한다. 이때 동전의 다음 위치에 대한 조건 처리를 해주어야 한다.

• 두 동전의 위치가 모두 보드 범위 밖으로 나가는 경우
• 하나의 동전만 보드 범위 밖으로 나가는 경우
• 다음 위치가 벽인 경우

이 케이스들에 대한 처리를 깔끔하게 해주면 문제가 바로 해결된다.

• n, m을 입력받는다.
• board를 입력받는다.
• q를 deque로 선언한다.
• 임시 변수 tmp를 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> m번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 board[i][j]가 o일 경우, tmp에 i와 j를 넣는다.
• q에 (tmp[0], tmp[1], tmp[2], tmp[3], 0)를 넣는다.
• dy, dx 리스트를 서동북남 순서로 저장한다.
• bfs함수를 선언한다.
  -> q가 존재하는 동안 반복하는 while문을 돌린다.
  --> y1, x1, y2, x2, cnt를 q에서 빼낸다.
  --> 만약 cnt가 10이상일 경우, while문을 종료한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny1, nx1, ny2, nx2를 y1+dy[i], x1+dx[i], y2+dy[i], x2+dx[i]로 선언한다.
  ---> 만약 not (0<=ny1<n and 0<=nx1<m) and not (0<=ny2<n and 0<=nx2<m)의 조건, 즉 두 동전이 모두 보드 밖으로 나간 경우, 다음 반복으로 넘어간다.
  ---> 만약 not (0<=ny1<n and 0<=nx1<m)의 조건, 즉 하나의 동전만 보드 밖으로 나간 경우, cnt+1을 반환한다.
  ---> 만약 not (0<=ny2<n and 0<=nx2<m)의 조건, 즉 하나의 동전만 보드 밖으로 나간 경우, cnt+1을 반환한다.
  ---> 만약 board[ny1][nx1]=='#'의 조건, 즉 동전의 다음 위치가 벽일 경우, ny1, nx1을 y1, x1로 갱신한다.
  ---> 만약 board[ny2][nx2]=='#'의 조건, 즉 동전의 다음 위치가 벽일 경우, ny2, nx2를 y2, x2로 갱신한다.
  ---> q에 (ny1, nx1, ny2, nx2, cnt+1)를 넣는다.
  -> -1을 반환한다.
• answer를 bfs()의 반환값으로 선언한다.
• answer를 출력한다.

Code

import collections
n, m=map(int, input().split())
board=[list(str(input())) for _ in range(n)]
q=collections.deque()
tmp=[]
for i in range(n):
    for j in range(m):
        if board[i][j]=='o':
            tmp.append(i)
            tmp.append(j)
q.append((tmp[0], tmp[1], tmp[2], tmp[3], 0))
dy, dx=[0, 0, -1, 1], [-1, 1, 0, 0]
def bfs():
    while q:
        y1, x1, y2, x2, cnt=q.popleft()
        if cnt>=10:
            break
        for i in range(4):
            ny1, nx1, ny2, nx2=y1+dy[i], x1+dx[i], y2+dy[i], x2+dx[i]
            if not (0<=ny1<n and 0<=nx1<m) and not (0<=ny2<n and 0<=nx2<m):
                continue
            if not (0<=ny1<n and 0<=nx1<m):
                return cnt+1
            if not (0<=ny2<n and 0<=nx2<m):
                return cnt+1
            if board[ny1][nx1]=='#':
                ny1, nx1=y1, x1
            if board[ny2][nx2]=='#':
                ny2, nx2=y2, x2
            q.append((ny1, nx1, ny2, nx2, cnt+1))
    return -1
answer=bfs()
print(answer)