백준 알고리즘 13460 (구슬 탈출 1,2) - python

[문제] 백준 알고리즘 13459 (구슬 탈출)

> https://www.acmicpc.net/problem/13459

13459번: 구슬 탈출

[문제] 백준 알고리즘 13460 (구슬 탈출 2)

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

13460번: 구슬 탈출 2

 

사실 구슬 탈출 1,2는 거의 문제가 같다. 다른 점은 가능/불가능 출력인가 횟수 출력인가의 차이이다.

BFS 관련 문제를 제대로 이해한 건 처음이라, 다른 분의 설명을 참고해서 분석했다.

참고 : https://rebas.kr/724 , 진짜 훌륭하게 접근 설명을 해놓으셨음. 

나는 내 나름 이해한대로 수정한 코드를 주석 처리로 설명해야겠다.

 

내가 이해한 DFS와 BFS의 차이를 간략히 요약해보자면,

[DFS] : Depth-First-Search, Stack(Last-In-First-Out)과 재귀 함수를 활용하여 depth 기준 먼저 탐색

[BFS] : Breadth-First-Search, Queue(First-In-First-Out)와 While문을 활용하여 breadth 기준 먼저 탐색

 

[Code]

N, M = map(int, input().split())
B = [list(input().rstrip()) for _ in range(N)]  # Board
dx = [-1, 1, 0, 0]  # x축 움직임
dy = [0, 0, -1, 1]  # y축 움직임
queue = []  # BFS : queue 활용
# Red(rx,ry)와 Blue(bx,by)의 탐사 여부 체크
visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]

def pos_init():
    rx, ry, bx, by = 0, 0, 0, 0  # 초기화
    for i in range(N):
        for j in range(M):
            if B[i][j] == 'R':
                rx, ry = i, j
            elif B[i][j] == 'B':
                bx, by = i, j
    # 위치 정보와 depth(breadth 끝나면 +1)
    queue.append((rx, ry, bx, by, 1))
    visited[rx][ry][bx][by] = True

def move(x, y, dx, dy):
    cnt = 0  # 이동 칸 수
    # 다음이 벽이거나 현재가 구멍일 때까지
    while B[x+dx][y+dy] != '#' and B[x][y] != 'O':
        x += dx
        y += dy
        cnt += 1
    return x, y, cnt

def solve():
    pos_init()  # 시작 조건
    while queue:  # BFS : queue 기준
        rx, ry, bx, by, depth = queue.pop(0)
        if depth > 10:  # 실패 조건
            break
        for i in range(4):  # 4방향 이동 시도
            nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])  # Red
            nbx, nby, bcnt = move(bx, by, dx[i], dy[i])  # Blue
            if B[nbx][nby] != 'O':  # 실패 조건이 아니면
                if B[nrx][nry] == 'O':  # 성공 조건
                    print(depth)
                    return
                if nrx == nbx and nry == nby:  # 겹쳤을 때
                    if rcnt > bcnt:  # 이동거리가 많은 것을
                        nrx -= dx[i]  # 한 칸 뒤로
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]
                # breadth 탐색 후, 탐사 여부 체크
                if not visited[nrx][nry][nbx][nby]:
                    visited[nrx][nry][nbx][nby] = True
                    # 다음 depth의 breadth 탐색 위한 queue
                    queue.append((nrx, nry, nbx, nby, depth+1))
    print(-1)  # 실패 시

solve()