문제 : https://www.acmicpc.net/problem/16197

문제요약

• 기본적으로는 동전이 N * M 크기의 보드 바깥으로 벗어날 수 있는지를 찾는 탐색 문제이다.

• 특이한 점은 동전이 2개가 주어지며, 동전 2개가 동시에 바깥으로 벗어나면 안된다는 것이다.

• 즉 각 동전별로 탐색을 진행해야 하며, 동전이 동시에 떨어지는 것인지 체크해야하는 과정이 추가된다.

접근

• 무한루프 없이 10번 넘게 이동하면 -1을 출력한다. -> 방문체크 필요 없음

• 이동해야하는 최소 횟수를 출력해야한다. -> BFS 탐색

풀이 과정

1. N * M 크기의 board를 입력받는다. 입력 받을 때 코인의 위치를 별도로 저장한다.

2. 저장한 코인의 위치를 토대로 BFS 탐색을 한다.
   • 코인이 모두 board 좌표 안에 존재해야 한다. (조건문 체크)
   • 상하좌우 4방향으로 코인을 움직이고, 움직이는 것이 가능한 경우 큐에 추가해서 다음 탐색을 진행 (방문체크 없음)
3. (2)의 조건문 체크가 False인 경우 적어도 코인 중 하나가 board 좌표 안에 남아있는지 확인한다. (조건문 체크)
   • 조건문이 참이라면 즉시 count + 1 값을 반환한다.
   • 조건문이 거짓이라면 넘어간다. (둘다 떨어진 경우이므로)

어려웠던 점

- 1번
####
#oo.
####

위와 같은 상황일 때, 두 코인은 왼쪽 방향으로는 이동할 수 없다. (1번) 반면에 오른쪽 방향으로 이동하는 것은 가능하다. (2번)

- 2번
####
#.oo
####

이러한 처리를 어떻게 할 수 있느냐를 고민하는 것에 많은 시간이 소요되었다. 단순히 다음에 이동할 장소가 . 일때만 코인을 움직이도록 하면 2번 상황을 구현할 수 없다. 반대로 이동할 장소가 #이 아닐때 코인을 움직이도록 하면 두 코인의 위치가 겹치는 문제가 발생한다.

해결책

우선 코인이 이동할 장소가 벽이 아니면 무조건 이동할 수 있다고 가정한다. 두 코인이 이동할 위치를 정하고, 두 코인이 서로 다른 위치에 있다는 것을 조건문을 통해 확인한 후 큐에 추가하는 방식을 사용하였다.

코드

import sys
from collections import deque

input = sys.stdin.readline

def BFS(coins):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    que = deque()
    que.append((coins[0][0], coins[0][1], coins[1][0], coins[1][1], 0))
    while que:
        x1, y1, x2, y2, count = que.popleft()
        if count == 10:
            return -1
        for n in range(4):
            xx1 = x1 + dx[n]
            yy1 = y1 + dy[n]
            xx2 = x2 + dx[n]
            yy2 = y2 + dy[n]
            # 코인이 다음에 이동할 위치를 저장함
            nx1, ny1, nx2, ny2 = x1, y1, x2, y2
            if 0<=xx1<N and 0<=yy1<M and 0<=xx2<N and 0<=yy2<M:
            	# 이동할 수 있을때만 nx, ny를 xx, yy로 초기화
                if board[xx1][yy1] != '#':
                    nx1, ny1 = xx1, yy1
                if board[xx2][yy2] != '#':
                    nx2, ny2 = xx2, yy2
                # nx, ny가 모두 겹치면 안됨
                if nx1 != nx2 or ny1 != ny2:
                    que.append((nx1, ny1, nx2, ny2, count+1))
            else:
                # 둘 중 하나는 안에 남아있어야 함
                if (0<=xx1<N and 0<=yy1<M) or (0<=xx2<N and 0<=yy2<M):
                    return count + 1
    return -1


N, M = map(int, input().split())
board = []
coins = []
for i in range(N):
    temp = list(map(str, input().rstrip()))
    for j in range(M):
        if temp[j] == 'o':
            coins.append((i, j))
    board.append(temp)

print(BFS(coins))