문제

빈 공간, 벽, 그리고 두 명의 플레이어 A와 B의 시작지점이 주어졌을 때, A와 B가 서로의 위치를 바꾸는데 드는 턴의 최솟값을 구하는 프로그램을 작성하시오.

한 턴에 하나 또는 두 명의 플레이어는 움직일 수 있다. 한 번 움직인다는 것은 현재 위치에서 위, 왼쪽, 오른쪽, 아래, 4가지 대각선 중 하나로 이동하는 것이다. 하지만, 벽으로 이동하거나, 게임 판을 벗어나게 이동할 수는 없다. 그리고 각 턴의 마지막에 두 플레이어는 같은 곳에 있으면 안 된다. 한 턴에 두 플레이어가 서로 교차하는 경로를 가지는 것은 안 된다. 경로를 서로 교차하는 것이라는 것은 한 턴에 서로의 위치를 바꾸는 것을 의미한다.

예를 들어, A가 게임 판의 가장 왼쪽 위에 있고, B가 바로 오른쪽에 있다고 해보자. 만약, B가 왼쪽으로 움직인다면, A는 오른쪽으로 움직일 수 없다. 이때가 경로가 교차하는 것이다. 하지만, B가 왼쪽을 제외한 다른 방향으로 이동한다면, A는 오른쪽으로 이동할 수 있다.

A가 (0, 0)에 있고, B가 (0, 1)에 있을 때, A가 오른쪽 아래방향 대각선으로 움직이고, B가 왼쪽 아래방향 대각선으로 움직일 때, (0.5, 0.5)에서 만나기는 하지만, 이것은 경로가 교차하는 것이 아니다.

입력

첫째 줄에 게임 판의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 게임 판의 상태가 주어진다. 빈 공간은 ., 벽은 X, A의 위치는 A, B의 위치는 B와 같이 표시된다.

출력

첫째 줄에 A와 B가 서로의 위치를 바꾸는데 드는 최소 턴을 출력한다. 만약 바꿀 수 없으면 -1을 출력한다.

예제

Example 1:

Input: 
3 9
XXXXXXXXX
A.......B
XXXX.XXXX
Output: 
8

조건

시간 제한 : 2초

메모리 제한 : 128 MB

풀이과정

풀이 1

BFS로 해결하였다. 로직 자체는 문제에서 시키는 대로만 구현하면 되기 때문에 어렵지 않았다. 하지만, 72%쯤에서 시간 초과가 떴다.

기존 코드는 A와 B가 움직인다고 생각하고 미리 결정한 뒤에($8\times 8$) A만, B만, AB둘다의 경우를 대입해서 ($8\times 8 \times 3 = 192$) 해결하였다.

하지만, 이렇게하면 A만, B만 움직이는 경우에도 필요없는 계산을 하게 된다. 따라서 AB둘다($8\times 8$) , A만($8$), B만($8$) 이렇게 따로 계산하면($8\times 8+8+8 = 80$)이 된다. 그만큼 시간 복잡도가 차이가 크단 소리!

from collections import deque, defaultdict
import copy
import sys
n, m = map(int, input().split())

graph = []

a = [0, 0]
b = [0, 0]
for x in range(n):
    sub = list(input())
    graph.append(sub)
    for y in range(m):
        if sub[y] == 'A':
            a[0], a[1] = x, y
        elif sub[y] == 'B':
            b[0], b[1] = x, y

visited = defaultdict(bool)
visited[(tuple(a), tuple(b))] = True

q = deque()
q.append((a, b, 0))

dx = [0,1,0,-1,1,-1,-1,1]
dy = [1,0,-1,0,1,-1,1,-1]

target_A = copy.deepcopy(b)
target_B = copy.deepcopy(a)

while q:
    A, B, level = q.popleft()

    # AB 둘다 움직이기
    for k in range(8):
        NA = [A[0]+dx[k], A[1]+dy[k]]
        for p in range(8):
            NB = [B[0]+dx[p], B[1]+dy[p]]
            # 벗어나면 안됨
            if 0 <= NA[0] < n and 0 <= NA[1] < m and 0 <= NB[0] < n and 0 <= NB[1] < m:
                # X도 가면 안됨
                if graph[NA[0]][NA[1]] != 'X' and graph[NB[0]][NB[1]] != 'X':
                    # 교차도 안됨
                    if not (NA == B and NB == A) and not (NA == NB):
                        if not visited[(tuple(NA), tuple(NB))]:
                            visited[(tuple(NA), tuple(NB))] = True
                            if NA == target_A and NB == target_B:
                                print(level+1)
                                sys.exit()
                            q.append((NA, NB, level+1))
    # A만 움직이기
    for k in range(8):
        NA = [A[0]+dx[k], A[1]+dy[k]]
        NB = B
        # 벗어나면 안됨
        if 0 <= NA[0] < n and 0 <= NA[1] < m and 0 <= NB[0] < n and 0 <= NB[1] < m:
            # X도 가면 안됨
            if graph[NA[0]][NA[1]] != 'X' and graph[NB[0]][NB[1]] != 'X':
                # 교차도 안됨
                if not (NA == B and NB == A) and not (NA == NB):
                    if not visited[(tuple(NA), tuple(NB))]:
                        visited[(tuple(NA), tuple(NB))] = True
                        if NA == target_A and NB == target_B:
                            print(level+1)
                            sys.exit()
                        q.append((NA, NB, level+1))
    # B만 움직이기
    for k in range(8):
        NA = A
        NB = [B[0]+dx[k], B[1]+dy[k]]
        # 벗어나면 안됨
        if 0 <= NA[0] < n and 0 <= NA[1] < m and 0 <= NB[0] < n and 0 <= NB[1] < m:
            # X도 가면 안됨
            if graph[NA[0]][NA[1]] != 'X' and graph[NB[0]][NB[1]] != 'X':
                # 교차도 안됨
                if not (NA == B and NB == A) and not (NA == NB):
                    if not visited[(tuple(NA), tuple(NB))]:
                        visited[(tuple(NA), tuple(NB))] = True
                        if NA == target_A and NB == target_B:
                            print(level+1)
                            sys.exit()
                        q.append((NA, NB, level+1))
print(-1)