[백준] 13460 구슬탈출2

---

 

최소한의 횟수로 빨간 구슬을 구멍으로 빼내는 문제이다. '최소한'이라는 단어에서 BFS를 사용해야 한다고 생각 해냈다. 하지만 구슬이 움직이는 방법에 대해서 고민하다 시도 조차 하지 못하고 포기했다.

 

다른 분들이 작성한 문제 해결 방법 참고하였다.

 

• 각각의 공은 동시에 움직이지만 겹쳐질 수 없다. 
• 파란공이 구멍에 빠지면 반드시 실패한 것이다. 동시에 빠져도 그러하다.
• 다음 움직임은 공이 더이상 이동할 수 없을 때 가능하다.
• 움직임이 10회가 초과하면 실패한 것으로 간주한다.

 

알고리즘 진행 중 빨간공과 파란공의 위치가 겹쳐지게 되는 경우 각 공의 이동 횟수를 구해서 더 큰 쪽이 늦게 도착했기 때문에 이전 상태로 되돌린다.

 

파란공이 먼저 혹은 동시에 구멍에 빠질 경우 무시한다

 

공을 이동시킬 경우 벽에 부딪혀 움직일 수 없을 때 까지 수행한다.

 

소스 코드

파이썬

from sys import stdin
from collections import deque

readline = stdin.readline

WALL = 0
PATH = 1
TARGET = 2
RED = 3
BLUE = 4

def main():
    N, M = map(int, readline().split())

    graph = [[0] * M for _ in range(N)]

    for i in range(N):
        line = readline().strip()
        for j in range(len(line)):
            if line[j] == "#":
                graph[i][j] = WALL
            elif line[j] == "O":
                graph[i][j] = TARGET
            else:
                graph[i][j] = PATH
                if line[j] == "R":
                    red = [i, j]
                elif line[j] == "B":
                    blue = [i, j]

    bfs(graph, red, blue, N, M)

dcol = (0, 0, 1, -1)
drow = (1, -1, 0, 0)

def bfs(graph, red, blue, N, M):
    visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]
    visited[red[0]][red[1]][blue[0]][blue[1]] = True

    q = deque()

    q.append([*red, *blue, 0])

    while q:
        r_row, r_col, b_row, b_col, d = q.popleft()
        
        if d >= 10:
            break

        for i in range(4):
            nr_row, nr_col, rc = move(graph, r_row, r_col, d, drow[i], dcol[i])
            nb_row, nb_col, bc = move(graph, b_row, b_col, d, drow[i], dcol[i])

            if graph[nb_row][nb_col] == TARGET:
                continue
            
            if graph[nr_row][nr_col] == TARGET:
                print(d+1)
                return

            if nb_row == nr_row and nb_col == nr_col:
                if rc > bc:
                    nr_row -= drow[i]
                    nr_col -= dcol[i]
                else:
                    nb_row -= drow[i]
                    nb_col -= dcol[i]

            if not visited[nr_row][nr_col][nb_row][nb_col]:
                visited[nr_row][nr_col][nb_row][nb_col] = True
                q.append([nr_row, nr_col, nb_row, nb_col, d+1])
    
    print(-1)


def move(graph, row, col, d, dr, dc):
    
    while graph[row+dr][col+dc] != WALL and graph[row][col] != TARGET:
        row += dr
        col += dc
        d += 1

    return row, col, d


if __name__ == '__main__':
    main()

 

visited를 빨간 공과 파란 공 각각 2개로 선언한 것이 아니라 4차원 배열로 선언한 것에 대해서

 

공을 움직일 때 각 공은 이전에 지나갔던 지점으로 돌아갈 수 있다. 하지만 빨간 공과 파란 공 모두 지나갔던 지점을 다시 지나간다면 제자리를 돌고 있다는 것이기 때문에 각각 2개의 visited가 아닌 4차원 배열로 선언한다.