[백준] 13460: 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

이번 문제는 bfs로 풀었습니다. 구현 자체가 이전 문제들보다는 난이도 있어서 구현에 시간을 생각보다 많이 사용하였습니다.

사실 원래 dfs를 연습할 생각으로 문제를 보고 dfs로 풀어야지 라는 강박에 잡혀 시간을 허비하다가 다른 사람들의 코드를 참고하여 풀게 되었습니다.

그렇기에 주석을 이번엔 자세히 많이 첨부하면서 소스 코드를 되뇌이게 되었습니다.

 

from collections import deque

n , m  = map(int,input().split())

arr = [list(input()) for _ in range(n)] # 구슬이 탈출할 보드를 구현

q = deque()

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

for i in range(0,n):
    for j in range(0,m):
        if arr[i][j] == 'R':
            rx, ry = i,j
            arr[i][j] = '.'
            # .으로 변경하는 이유는 R과 B가 지나갈 수 있는 길을 .으로 통일하기 위함
            # x,y 좌표로 구슬의 위치를 추적하기 때문에 가능

		elif arr[i][j] == 'B':
            bx, by = i,j
            arr[i][j] = '.'
            
        elif arr[i][j] == 'O':
            ox, oy = i, j

q.append((rx,ry,bx,by,1))


def move(x, y ,dx, dy): # dx,dy를 돌면서 상하좌우 한방향으로 벽까지 가는 코드
    nx, ny = x, y
    moving = 0

    while True:
        if arr[nx+dx][ny+dy] == '.':
            nx += dx
            ny += dy
            moving += 1
        else:
            break
    return nx, ny, moving


min_ = -1
while q:
    x, y, a, b, cnt = q.popleft() # 큐 에서 pop
    if cnt > 10:
        continue

    for d in range(0,4):
        nx, ny, rcnt = move(x,y, dx[d], dy[d]) #빨간 구슬 움직임
        na, nb, bcnt = move(a,b, dx[d], dy[d]) # 같은 방향으로 파란 구술 움직임

        if arr[na+dx[d]][nb+dy[d]] == 'O': # 파란 구슬 먼저, 동시에 떨어질 경우 이어서 진행
            continue
            
        # 빨간 구슬이 먼저 떨어지면 종료
        # bfs이므로 첫 값이 가장 작음
        if arr[nx+dx[d]][ny+dy[d]] == 'O' and cnt <= 10: 
            if min_ == -1:
                min_ = cnt
                break

		# 구슬은 같은 위치에 있을 수 없으므로
        # 더 늦게 도착한 구슬을 한칸 뒤로 이동
        if nx == na and ny == nb:
            if rcnt > bcnt:
                nx -= dx[d]
                ny -= dy[d]
            else:
                na -= dx[d]
                nb -= dy[d]
        
        # 구슬 모두 움직임이 없는 경우는 큐에 push하지 않음
        if x == nx and y == ny and a == na and b == nb:
            continue
        q.append((nx,ny,na,nb,cnt+1))
    if min_ != -1:
        break

print(min_)

 

 

참고

https://2hs-rti.tistory.com/entry/%EB%B0%B1%EC%A4%80-13460%EB%B2%88-%EA%B5%AC%EC%8A%AC-%ED%83%88%EC%B6%9C-2-%ED%8C%8C%EC%9D%B4%EC%8D%AC