[BFS] 백준#13460: 구슬 탈출2/Python

📝 문제

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

13460번: 구슬 탈출 2

💡 접근법

BFS 알고리즘과 큐(Queue) 자료구조를 활용하여 문제를 해결하였습니다. 빨간 공과 파란 공의 좌표 정보와 보드를 기울인 횟수를 저장하는 큐가 빌 때까지 다음 작업을 반복합니다. 공이 움직일 수 있을 때까지 반복문을 활용하여 상하좌우 방향으로 움직이게 하며, 보드를 기울인 방향으로 공이 모두 움직였다면 큐에 공들의 좌표와 기울인 횟수를 업데이트합니다. 이 과정에서 다음 2가지 종료 조건 중 하나라도 만족하면 종료합니다.

• 첫째, 보드를 기울인 횟수가 \(10\)보다 큰 경우
• 둘째, 보드를 기울인 횟수가 \(10\)보다 작고 빨간색 공이 구멍에 들어간 경우

위의 \(2\)가지 조건을 모두 만족하지 않으면 큐에 데이터를 추가하지 못합니다. 이는 결국 빨간 공만을 구멍에 통과시킬 수 없다는 의미이기 때문에 \(-1\)을 출력합니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline
from collections import deque

def bfs(rx, ry, bx, by):
    q = deque()
    q.append((rx, ry, bx, by, 0))
    while q:
        rx, ry, bx, by, cnt = q.popleft()
        for dx, dy in d:
            nrx, nry, r_cnt = move(rx, ry, dx, dy)
            nbx, nby, b_cnt = move(bx, by, dx, dy)
            # Blue 공이 먼저 구멍에 들어갈 시, 다른 방향으로 이동
            if board[nbx + dx][nby + dy] == 'O':
                continue
            # Red 공이 구멍에 들어갈 시, 움직인 횟수 1 증가하고 종료(단, 10회 미만인 경우)
            if board[nrx + dx][nry + dy] == 'O' and cnt < 10:
                return cnt + 1
            # Red 공과 Blue 공이 만날 시, 먼저 도착한 공이 자리 차지
            if nrx == nbx and nry == nby:
                # Red 공이 먼저 도착 시, Blue 공을 한 칸 뒤로 이동
                if r_cnt < b_cnt:
                    nbx -= dx
                    nby -= dy
                else:
                    nrx -= dx
                    nry -= dy
            # 어떤 공도 움직이지 않는 경우
            if nrx == rx and nry == ry and nbx == bx and nby == by:
                continue

            if cnt < 10:
                q.append((nrx, nry, nbx, nby, cnt + 1))
            else:
                return -1
    return -1

def move(x, y, dx, dy):
    nx = x
    ny = y
    move_cnt = 0
    # 한 방향으로 이동할 수 있을 때까지 이동시키기
    while True:
        if board[nx+dx][ny+dy] != '#' and board[nx+dx][ny+dy] != 'O':
            nx += dx
            ny += dy
            move_cnt += 1
        else:
            break
    return nx, ny, move_cnt

if __name__ == '__main__':
    N, M = map(int, input().split())
    board = [list(input().rstrip()) for _ in range(N)]
    rx = ry = bx = by = ""
    for i in range(N):
        for j in range(M):
            if rx and ry and bx and by:
                break
            if board[i][j] == 'R':
                rx, ry = i, j
                continue
            if board[i][j] == 'B':
                bx, by = i, j
                continue

    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    answer = bfs(rx, ry, bx, by)
    print(answer)

2) 해설

(1) 패키지 import

import sys; input = sys.stdin.readline

파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.

from collections import deque

큐(queue) 자료구조를 사용하기 위해 deque 모듈을 불러왔습니다.

(2) BFS 알고리즘

def bfs(rx, ry, bx, by):
    q = deque()
    q.append((rx, ry, bx, by, 0))
    while q:
        rx, ry, bx, by, cnt = q.popleft()
        for dx, dy in d:
            nrx, nry, r_cnt = move(rx, ry, dx, dy)
            nbx, nby, b_cnt = move(bx, by, dx, dy)
            # Blue 공이 먼저 구멍에 들어갈 시, 다른 방향으로 이동
            if board[nbx + dx][nby + dy] == 'O':
                continue
            # Red 공이 구멍에 들어갈 시, 움직인 횟수 1 증가하고 종료(단, 10회 미만인 경우)
            if board[nrx + dx][nry + dy] == 'O' and cnt < 10:
                return cnt + 1
            # Red 공과 Blue 공이 만날 시, 먼저 도착한 공이 자리 차지
            if nrx == nbx and nry == nby:
                # Red 공이 먼저 도착 시, Blue 공을 한 칸 뒤로 이동
                if r_cnt < b_cnt:
                    nbx -= dx
                    nby -= dy
                else:
                    nrx -= dx
                    nry -= dy
            # 어떤 공도 움직이지 않는 경우
            if nrx == rx and nry == ry and nbx == bx and nby == by:
                continue

            if cnt < 10:
                q.append((nrx, nry, nbx, nby, cnt + 1))
            else:
                return -1
    return -1

BFS 알고리즘을 활용한 로직과 공을 움직이는 로직을 각각 다른 함수로 나누어 작성하였습니다. 먼저, BFS 알고리즘을 활용한 로직입니다.

• 2~5번째 라인
  • 큐에 공들의 좌표와 보드를 기울인 횟수를 저장하고, 큐가 빌 때까지 아래의 과정 반복
  • 상하좌우 방향으로 보드를 기울이고, 해당 방향으로 움직일 수 있을 때까지 공들을 최대한 움직이기
• 10~14번째 라인
  • 파란 공이 빨간 공보다 먼저 구멍에 들어가면 안 되기 때문에, 다른 방향으로 보드 기울이기
  • 보드를 기울인 횟수가 \(10\)보다 작을 때, 파란 공은 구멍에 들어가지 않고 빨간 공이 구멍에 들어갔다면, 기존에 보드를 기울인 횟수에 \(1\)을 더해주고 함수 종료
• 16번째 라인
  • 만약 파란 공과 빨간 공이 같은 곳에 도착했다면, 먼저 도착한 공은 해당 좌표에 머무르게 하고, 늦게 도착한 공의 좌표는 기울인 방향의 반대 방향으로 1칸 이동

(3) Move 함수

def move(x, y, dx, dy):
    nx = x
    ny = y
    move_cnt = 0
    # 한 방향으로 이동할 수 있을 때까지 이동시키기
    while True:
        if board[nx+dx][ny+dy] != '#' and board[nx+dx][ny+dy] != 'O':
            nx += dx
            ny += dy
            move_cnt += 1
        else:
            break
    return nx, ny, move_cnt

보드를 기울인 방향으로 공을 최대한 움직이는 함수입니다. 기울인 방향으로 공이 이동하려 했을 때, 해당 위치가 벽이나 구멍이 아닌 경우, 좌표를 업데이트하고 공이 움직인 횟수를 \(1\) 증가시킵니다.

(4) 메인함수

if __name__ == '__main__':
    N, M = map(int, input().split())
    board = [list(input().rstrip()) for _ in range(N)]
    rx = ry = bx = by = ""
    for i in range(N):
        for j in range(M):
            if rx and ry and bx and by:
                break
            if board[i][j] == 'R':
                rx, ry = i, j
                continue
            if board[i][j] == 'B':
                bx, by = i, j
                continue

    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    answer = bfs(rx, ry, bx, by)
    print(answer)

메인 함수입니다. 빨간 공과 파란 공의 좌표를 찾을 때까지 이중 반복문을 돌립니다.

✅ 채점 결과

정답 확인

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_13460.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

📚 참고할 만한 포스팅

문제 풀이에 사용한 BFS 알고리즘과 큐 자료구조에 대한 자세한 설명은 아래 포스팅을 참고해 주세요.

https://heytech.tistory.com/56

[알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)

https://heytech.tistory.com/54

큐(Queue) 자료구조 이해(+ Python)

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.