[백준(BOJ)] 13460번 : 구슬 탈출 2 - PYTHON[파이썬]

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

13460번: 구슬 탈출 2

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

 

빨간 구슬의 좌표와 파란 구슬의 좌표를 담을 변수를 설정해준다.

 

그리고 현재 빨간 구슬의 좌표와 파란 구슬의 좌표를 찾아내어 변수에 저장해주고 큐에 추가한다.

그리고 bfs를 돌려준다. 10번 이상으로 움직였을 시는 멈추고 아닐 시,

move 메서드를 사용하여 구슬을 움직여준다. 언제까지?

구멍이 아니거나 벽이 아닐 때까지.

 

그리고 10번 안에 빨간 구슬이 구멍에 떨어지면 count를 return 해주고 종료한다.

안 떨어지면 방문 처리하고, 다시 q에 현재 좌표를 추가해주고 반복해준다.

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(input().strip()) for _ in range(N)]
visited = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
q = deque()

rx, ry, bx, by = 0, 0, 0, 0

for i in range(N):
    for j in range(M):
        if arr[i][j] == 'R':
            rx, ry = i, j
        if arr[i][j] == 'B':
            bx, by = i, j

q.append([rx, ry, bx, by, 1])
visited.append([rx, ry, bx, by])


def move(x, y, i, j):
    count = 0
    while arr[x+i][y+j] != '#' and arr[x][y] != 'O':
        x += i
        y += j
        count += 1
    return x, y, count


def bfs():
    while q:
        rx, ry, bx, by, cnt = q.popleft()

        if cnt > 10:
            break
        for i in range(4):
            nrx, nry, rCnt = move(rx, ry, dx[i], dy[i])
            nbx, nby, bCnt = move(bx, by, dx[i], dy[i])

            if arr[nbx][nby] == 'O':
                continue

            if arr[nrx][nry] == 'O':
                return cnt

            if nrx == nbx and nry == nby:
                if rCnt > bCnt:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            if [nrx, nry, nbx, nby] not in visited:
                visited.append([nrx, nry, nbx, nby])
                q.append([nrx, nry, nbx, nby, cnt+1])
    return -1


print(bfs())

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

진짜 어렵다....

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!