백준 13460번: 구슬 탈출2 (Python)

접근

처음에는 DFS로 접근해서 풀려고 하다가 BFS로 접근하여 조금 더 간단하게 풀 수 있었던 것 같다.

현재 위치 및 방향을 입력하여 움직일 수 있는 끝까지 이동시키고, 이동 거리 및 이동 위치를 리턴하는 move 함수,
BFS 알고리즘, queue를 이용하여 빨간 구슬이 최종 위치에 먼저 도달하면 depth를 리턴하고, 파란 구슬이 먼저 최종 위치에 도달하거나 10번 이내에 빨간 구슬을 상자에서 빼낼 수 없을 경우에는 -1을 리턴하는 solve 함수 두가지를 이용하여 정답을 구할 수 있었다.

코드

from collections import deque

# 구슬의 이동 방향
rc = [1, 0, -1, 0]
cc = [0, 1, 0, -1]


# 구슬의 위치 및 이동 방향을 입력 받아 이동 위치 및 이동 거리를 리턴하는 함수
def move(r, c, di):
    cnt = 0
    while matrix[r + rc[di]][c + cc[di]] != "#" and matrix[r][c] != "O":
        r += rc[di]
        c += cc[di]
        cnt += 1
    return r, c, cnt


# 두 구슬의 위치를 입력 받아 BFS 알고리즘을 이용하여 문제를 해결하는 함수
def solve(rr, cr, rb, cb):
    queue = deque([])
    # 처음 위치를 queue에 추가하고, visited 표시
    queue.append((rr, cr, rb, cb, 1))
    visited[rr][cr][rb][cb] = True
    while queue:
        rr, cr, rb, cb, depth = queue.popleft()
        # 10번 이내에 목적지에 도달하지 못할 경우 실패
        if depth > 10:
            break
        for di in range(4):
            # 4 방향으로 각 구슬 이동
            nrr, ncr, rcnt = move(rr, cr, di)
            nrb, ncb, bcnt = move(rb, cb, di)
            if matrix[nrb][ncb] != "O":
                if matrix[nrr][ncr] == "O":
                    # 빨간 구슬이 목적한 위치(구멍)에 도달할 경우 depth(횟수) 리턴
                    return depth
                if nrr == nrb and ncr == ncb:
                    # 빨간 구슬과 파란 구슬이 같은 위치에 위치할 경우, 이동거리가 더 짧은 쪽을 한칸 복귀
                    if rcnt > bcnt:
                        nrr -= rc[di]
                        ncr -= cc[di]
                    else:
                        nrb -= rc[di]
                        ncb -= cc[di]
                if not visited[nrr][ncr][nrb][ncb]:
                    # 이동된 위치가 visited 되지 않았을 경우 visited 표시하고, queue에 추가
                    visited[nrr][ncr][nrb][ncb] = True
                    queue.append((nrr, ncr, nrb, ncb, depth + 1))
    return -1


N, M = map(int, input().split())
matrix = [[""] * M for _ in range(N)]
for i in range(N):
    line_tmp = list(input())
    for j in range(M):
        if line_tmp[j] == "R":
            rr, cr = i, j
        if line_tmp[j] == "B":
            rb, cb = i, j
        matrix[i][j] = line_tmp[j]
visited = [[[[False] * M for _ in range(N)] for __ in range(M)] for ___ in range(N)]
res = solve(rr, cr, rb, cb)
print(res)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!