구슬 탈출 2 백준 13460번 BFS 시뮬레이션

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

문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

---

필요한 것을 생각 해보면 일단 어디를 이동 했는지 체크를 하는 변수가 하나 필요할 것입니다. 이게 없으면 BFS 탐색을 할때 무한 루프에 빠지는 경우가 발생하겠네요 그리고 빨간공과 파란공이 같은 위치에 있을 수가 없습니다. 그러면 한번 이동을 수행할때 각 공이 이동한 거리를 구하고 짧은 거리를 이동한 공을 먼저 위치 시키면 되겠네요

n, m = map(int,input().split())
map_list = []
for _ in range(n):
    map_list.append(list(map(str,input())))

n과 m을 넣고 지도를 저장할 리스트를 하만 들어줍시다. 그리고 지도는 입력받을때 띄워진게 아니라 하나의 문자열로 들어오기 때문에 map에 str을 지정해줘야 합니다. 뒤에 split는 당연히 들어갈 이유가 없고요

for x in range(n):
    for y in range(m):
        if map_list[x][y] == 'R':
            rsx, rsy = x, y
        if map_list[x][y] == 'B':
            bsx, bsy = x, y
        if map_list[x][y] == 'O':
            ox, oy = x, y

빨간공, 파란공, 구멍의 위치를 확인하기 위한 이중 for문 입니다.

def move(x, y, dx, dy):
    count = 0
    nx, ny = x, y
    while map_list[nx + dx][ny + dy] != '#' and map_list[nx][ny] != 'O':
        nx += dx
        ny += dy
        count += 1
    return nx,  ny, count

구슬이 끝까지 이동하는 함수입니다. x,y는 현재 방향이고 dx,dy는 진행 방향입니다.

이동한 위치가 #(벽)이거나 O(구멍)이 아닐때까지 계속해서 이동을 하는데 이때 count를 계산하는 이유는 빨간공과 파란공이 동시에 같은 곳에 위치할 경우 먼저 오는 것을 구하기 위해서입니다. count가 짧은게 먼저 도착해있겠지요

그렇게 이동한 좌표와 거기까지 가는데 걸린 count를 반환을 합니다. 만약 나중에 서술하겠지만 공의 위치가 겹칠때 count가 큰것에다 dx,dy를 하나씩 빼주면 되겠지요

    visited = {}
    moves = [(-1,0),(1,0),(0,-1),(0,1)]
    visited[(rsx,rsy)] = 1
    count = 0
    s = [[rsx,rsy,bsx,bsy,count]]

방문기록과 이동할 수 있는 방향 4가지(상하좌우) 몇번 이동했는지 count

그리고 이동을 관리할 s에다가 빨간공의 위치와 파란공 그리고 count를 넣어줍니다.

while s:
        rx, ry, bx, by, count = s.pop(0)
        if count >= 10:
            print(-1)
            break
        for dx, dy in moves:
            rrx, rry, rcnt = move(rx,ry,dx,dy)
            bbx, bby, bcnt = move(bx,by,dx,dy)

            if map_list[bbx][bby] != 'O':
                if rrx == ox and rry == oy:
                    print(count + 1)
                    break
                if rrx == bbx and rry == bby:
                    if rcnt > bcnt:
                        rrx, rry = rrx-dx, rry-dy
                    else:
                        bbx, bby = bbx-dx, bby-dy
                if (rrx,rry,bbx,bby) in visited:
                    continue
                else:
                    visited[(rrx,rry,bbx,bby)] = 1
                    s.append([rrx,rry,bbx,bby,count+1])

while문을 통해서 반복을 합니다. 초기 s에서는 일단 빨간공과 파란공 그리고 위치에서 시작을 합시다. 그리고 count가 10회가 넘어가면 종료를 합니다.

moves에는 4방향으로의 방향이 들어 있습니다. 이제 각 움직임이 가능할때마다 조건을 만족하는지 확인을 하고 s에 넣는 식으로 작동을 합니다.

일단 이동을 한다음 빨간공과 파란공의 위치를 받아옵니다. 그리고 파란공이 구멍에 들어가지 않았을 경우에 조건을 확인을 합시다.

조건 1. 빨간공에 구멍에 잘 들어 갔을때. count를 1늘리고 출력을 하고 종료를 합니다.

조건 2. 빨간공과 파란공의 위치가 같을때 그러면 count를 비교해서 더 큰 녀석을 그 방향의 반대로 빼준 값을 넣어줍니다.

조건 3. 이미 방문한 경우 계속 pass

조건 4. 위 조건 3개 모두 해당하지 않을때 visited에 추가를 하고 s에 넣어서 다음으로 넘김

이렇게 4방향으로 돌고 나면 이동 s리스트에 남아 있는 녀석들을 차례대로 확인을 해봅니다.

생각했던 것 보다는 그렇게 어려운 문제는 아니었나 봅니다.