[BOJ] 13460: 구슬 탈출 2

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

13460번: 구슬 탈출 2

문제 해결

1. 리스트를 입력 받는다. -> 처음에 한 번에 받고 그 다음에 'R', 'B'를 찾아보려 했으나 그냥 포문안에서 입력 받으면서 찾아도 되겠다 싶어서 찾은 후엔 빈칸으로 바꿔주었다.

2. 이번 문제는 배열 하나하나씩 확인해가면서 푸는 게 좋기 때문에 bfs로 문제풀이

3. bfs는 주로 큐를 사용하는데, 넣은 순서대로 pop하기 위해서 deque 사용

4. 기울일 때 한 번 움직인 게 카운트 1은 아니지만, 나중에 어떤 구슬이 먼저 위치했는지 알기 위해서 moving을 사용해서 몇 번 이동했는지도 카운트해주었다. 한 번 기울였다는 건 queue에 같이 넣어줌 (count)

5. blue가 먼저 구멍에 들어갔을 땐 실패이므로 다시 진행 (continue)

6. red가 들어가면 count+1 리턴

7. 이전과 똑같은 자리라면 이미 방문한 거기 때문에 continue해주고 아니라면 다시 그 좌표를 queue에 입력

from collections import deque

# . # 0 R B => 빈칸, 장애물, 구멍, 빨간구슬, 파란구슬
N, M = map(int, input().split())
arr = []
red_x, red_y = 0, 0
blue_x, blue_y = 0, 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

for i in range(N):
    arr.append(list(input().strip()))
    for j in range(len(arr[i])):
        if arr[i][j] == 'R':
            red_x, red_y = i, j
            arr[i][j] = '.'
        elif arr[i][j] == 'B':
            blue_x, blue_y = i, j
            arr[i][j] = '.'

def move(x, y, dx, dy):
    next_x, next_y = x, y
    moving = 0
    while True:
        if arr[next_x+dx][next_y+dy] != '#' and arr[next_x+dx][next_y+dy] != 'O':
            next_x += dx
            next_y += dy
            moving += 1
        else:
            break

    return next_x, next_y, moving


def bfs():
    q = deque()
    q.append((red_x, red_y, blue_x, blue_y, 0))
    while q:
        rx, ry, bx, by, count = q.popleft()
        if count >= 10:
            break

        for k in range(4):
            next_rx, next_ry, Rmove = move(rx, ry, dx[k], dy[k])
            next_bx, next_by, Bmove = move(bx, by, dx[k], dy[k])

            if arr[next_bx+dx[k]][next_by+dy[k]] == 'O':
                continue

            if arr[next_rx+dx[k]][next_ry+dy[k]] == 'O':
                return (count+1)

            if next_rx == next_bx and next_ry == next_by:
                if Rmove > Bmove:
                    next_rx -= dx[k]
                    next_ry -= dy[k]
                else:
                    next_bx -= dx[k]
                    next_by -= dy[k]

            if next_rx == rx and next_ry == ry and next_bx == bx and next_by == by:
                continue

            q.append((next_rx, next_ry, next_bx, next_by, count+1))
    
    return -1

result = bfs()
print(result)

정말 열받았던,, 알고보니 x,y 를 잘못썼답니다 😇