백준 알고리즘 13460번 구슬탈출 풀이 with Python

문제 링크:https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

문제는 아래의 이미지와 같습니다.

백준 알고리즘 13460번 구슬탈출2

처음에 DFS(깊이 우선 탐색)으로 해결하려고 하였다가 문제에서 최소 몇 번 만에 탐색할 수 있는가를 물어서 이 문제는 BFS로 풀어야 함을 뒤늦게 알게 되었다. 그리고 방문한 것 역시 4차원 배열을 사용해야 함을 뒤늦게 깨닫게 되었다. 4차원 배열을 사용해야 하는 이유는 빨간 구슬의 x, y좌표와 파란 구슬의 x, y좌표를 각각 생각하여 그때의 방문 여부를 체크해야 하기 때문에 4차원 배열을 사용하게 되었다. 아래는 내가 해결한 코드이다.

def bfs(x1, y1, x2, y2, map1, c, O):
    n = len(map1)
    m = len(map1[0])
    queue = []
    queue.append([x1, y1, x2, y2, c])
    visit=[[[[0 for _ in range(m)] for _ in range(n)] for _ in range(m)] for _ in range(n)]
    global answer
    while (queue):
        x1, y1, x2, y2, c = queue.pop(0)
        if c > 10:
            return
        visit[x1][y1][x2][y2]=1
        dx = [-1, 0, 1, 0]
        dy = [0, -1, 0, 1]
        for i in range(4):
            flag1=0
            flag2=0
            flag=0
            nx1,ny1,nx2,ny2=[x1,y1,x2,y2]
            while (1):
                if flag1 == 1 and flag2 == 1:
                    break
                if flag1 == 0:
                    nx1 += dx[i]
                    ny1 += dy[i]
                if flag2 == 0:
                    nx2 += dx[i]
                    ny2 += dy[i]
                # 벽을 만났을 때
                if map1[nx1][ny1] == 1:
                    nx1 -= dx[i]
                    ny1 -= dy[i]
                    flag1 = 1
                if map1[nx2][ny2] == 1:
                    nx2 -= dx[i]
                    ny2 -= dy[i]
                    flag2 = 1
                # 구멍을 만나면
                if [nx1, ny1] == O:
                    flag = 2
                    flag1 = 1
                if [nx2, ny2] == O:
                    flag = 1
                    flag2 = 1
                    break
                # 구슬이 서로 만날 때
                if nx1 == nx2 and ny1 == ny2:
                    if flag1 == 0:
                        nx1 -= dx[i]
                        ny1 -= dy[i]
                        flag1 = 1
                    elif flag2 == 0:
                        nx2 -= dx[i]
                        ny2 -= dy[i]
                        flag2 = 1
            # 구슬중에 구멍에 들어간 것이 있을 때
            if flag == 1:
                continue
            elif flag == 2:
                answer=c
                return
            else:
                if visit[nx1][ny1][nx2][ny2]==0:
                    queue.append([nx1, ny1, nx2,ny2, c + 1])


n, m = map(int, input().split())
answer=-1
map1 = [[0 for _ in range(m)] for _ in range(n)]
B = [0, 0]
R = [0, 0]
O = [0, 0]
for i in range(n):
    s = input()
    for j in range(m):
        if s[j] == '#':
            map1[i][j] = 1
        elif s[j] == 'R':
            R = [i, j]
        elif s[j] == 'B':
            B = [i, j]
        elif s[j] == 'O':
            O = [i, j]
bfs(R[0], R[1], B[0], B[1], map1, 1, O)
print(answer)