파이썬으로 풀어보는 백준 13460번: 구슬 탈출 2 (삼성 SW 역량 테스트 기출 문제)

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

 

내 풀이:

def move(y, x, dirc):
    ny = y + dy[dirc]
    nx = x + dx[dirc]
    distance = 0
    while arr[ny][nx] == '.':
        distance += 1
        ny += dy[dirc]
        nx += dx[dirc]
    if arr[ny][nx] == 'O':
        return ny, nx, distance
    else:
        return ny - dy[dirc], nx - dx[dirc], distance
 
 
def BFS(Ry, Rx, By, Bx):
    q = [(Ry, Rx, By, Bx)]
    visited[Ry][Rx][By][Bx] = True
    cnt = 1
    while q and cnt <= 10:
        for i in range(len(q)):
            Ry, Rx, By, Bx = q.pop(0)
            for dirc in range(4):
                nRy, nRx, R_move = move(Ry, Rx, dirc)
                nBy, nBx, B_move = move(By, Bx, dirc)
 
                if arr[nBy][nBx] == 'O':
                    continue
                elif arr[nRy][nRx] == 'O':
                    return cnt
                else:
                    if nRy == nBy and nRx == nBx:
                        if R_move > B_move:
                            nRy -= dy[dirc]
                            nRx -= dx[dirc]
                        else:
                            nBy -= dy[dirc]
                            nBx -= dx[dirc]
 
                        if not visited[nRy][nRx][nBy][nBx]:
                            visited[nRy][nRx][nBy][nBx] = True
                            q.append((nRy, nRx, nBy, nBx))
                    else:
                        if not visited[nRy][nRx][nBy][nBx]:
                            visited[nRy][nRx][nBy][nBx] = True
                            q.append((nRy, nRx, nBy, nBx))
        cnt += 1
    return -1
 
 
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
 
N, M = map(int,input().split())
arr = [list(input()) for _ in range(N)]
visited = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]
for i in range(N):
    for j in range(M):
        if arr[i][j] == 'B':
            By = i
            Bx = j
            arr[i][j] = '.'
        elif arr[i][j] == 'R':
            Ry = i
            Rx = j
            arr[i][j] = '.'
 
print(BFS(Ry, Rx, By, Bx))

Python3, 60ms

이 문제의 핵심은 BFS를 구현할 때 visited를 어떻게 처리하느냐에 있다. 나는 어떤 순간의 빨간 공의 좌표와 파란 공의 좌표가 완전히 일치한 적이 있다면 이를 visited를 통해 걸러주었다. 총 4개의 좌표를 읽어 들여야 하기 때문에 4차원 배열을 만들어야 했다. 이후에는 일반적인 BFS 알고리즘을 구현하였다. 다만 주의해야 할 점 2가지 중 첫 번째는 공이 벽에 닿았을 때는 벽에 닿기 전의 좌표를 반환하여야 하고 구멍에 들어갔을 때는 구멍의 좌표를 반환해주어야 한다는 것이다. 두 번째로는 cnt를 하나씩 올릴 때 구멍에 도달한 순간의 cnt값과 cnt를 올려주는 순간을 잘못 배치하면 cnt가 11일 때도 답으로 처리될 수 있다. 만약 답안을 제출하고 69%에서 오답처리를 받았다면 앞서 언급한 실수가 있을 것이다.