[백준] 13459 구슬 탈출 python

www.acmicpc.net/problem/13459

13459번: 구슬 탈출

delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def backtrack(inboard, inred, inblue, ind=0, arr=[]):
    global result, delta
    if result == 1:
        return
    if ind == 10:
        return
    else:
        for i in range(4):
            tmp_board = [inboard[j][:] for j in range(N)]
            tmp_red = inred[:]
            tmp_blue = inblue[:]
            ############# move #############
            # direction 0:상,1:하, 2:좌, 3:우
            move_check = True
            while move_check:
                # 구슬 이동 없으면 break
                if tmp_red == [-1,-1] and tmp_blue == [-1,-1]:
                    break
                move_check = False
                rx, ry = tmp_red
                bx, by = tmp_blue
                drx = rx + delta[i][0]
                dry = ry + delta[i][1]
                dbx = bx + delta[i][0]
                dby = by + delta[i][1]
                # 벽, 구슬을 지나가면안됨
                # 구슬이 구멍에 닿으면 제거
                if tmp_board[drx][dry] == '.':
                    tmp_board[drx][dry] = 'R'
                    tmp_board[rx][ry] = '.'
                    tmp_red = [drx, dry]
                    move_check = True
                elif tmp_board[drx][dry] == 'O':
                    tmp_board[rx][ry] = '.'
                    tmp_red = [-1, -1]
                    move_check = True

                if tmp_board[dbx][dby] == '.':
                    tmp_board[dbx][dby] = 'B'
                    tmp_board[bx][by] = '.'
                    tmp_blue = [dbx, dby]
                    move_check = True
                elif tmp_board[dbx][dby] == 'O':
                    tmp_board[bx][by] = '.'
                    tmp_blue = [-1, -1]
                    move_check = True
            # if red만 없으면 result  1
            if tmp_red == [-1, -1] and tmp_blue != [-1, -1]:
                result = 1
            ########################################
            backtrack(tmp_board, tmp_red, tmp_blue, ind + 1, arr+[i])
    return



N, M = map(int, input().split())
# board 에서 구슬위치를 바꿔주어야하므로 list 나눠서 받음
board = []
red = [-1, -1]
blue = [-1, -1]
for i in range(N):
    tmp = list(input())
    board.append(tmp)
    for j in range(M):
        if tmp[j] == 'B':
            blue = [i, j]
        elif tmp[j] == 'R':
            red = [i, j]

result = 0
backtrack(board, red, blue)
print(result)

10번 이내에만 확인하면 되므로 모든 조합을 bruteforce로 구했다.

move라고 써있는 부분은 원래 함수로 구현했는데 tmp_red, tmp_blue의 값이 변하지 않아서 함수 안으로 가져왔다.

백트래킹이나 DFS는 같다고 쳐도, BFS로는 어떻게 구해야하는지 잘모르겠다.

---

# -*- conding: utf-8 -*-

'''
Author : gksrbans123@gmail.com
Date : 2021-03-29
URL : https://www.acmicpc.net/problem/13459
Type : ?
'''

import sys
from collections import deque

#sys.stdin = open("input.txt", "r")

n, m = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
q = deque()


def init():
    rx, ry, bx, by = [0] * 4  # 초기화 0, 0, 0, 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':  # board에 빨간 구슬이라면 좌표 값 저장
                rx, ry = i, j
            elif board[i][j] == 'B':  # board에 파란 구슬이라면 좌표 값 저장
                bx, by = i, j
    q.append((rx, ry, bx, by, 1))  # 위치 정보와 depth
    visited[rx][ry][bx][by] = True


def move(x, y, dx, dy):
    count = 0  # 이동한 칸 수
    # 다음 이동이 벽이거나 구멍이 아닐 때까지
    while board[x + dx][y + dy] != '#' and board[x][y] != 'O':
        x += dx
        y += dy
        count += 1
    return x, y, count


def bfs():
    init()
    while q:  # BFS -> queue, while
        rx, ry, bx, by, depth = q.popleft()  # FIFO
        if depth > 10:  # 10 이하여야 한다.
            break
        for i in range(len(dx)):  # 4방향으로 시도한다.
            next_rx, next_ry, r_count = move(rx, ry, dx[i], dy[i])  # RED
            next_bx, next_by, b_count = move(bx, by, dx[i], dy[i])  # BLUE

            if board[next_bx][next_by] == 'O':  # 파란 구슬이 구멍에 떨어지지 않으면(실패 X)
                continue
            if board[next_rx][next_ry] == 'O':  # 빨간 구슬이 구멍에 떨어진다면(성공)
                print(1)
                return
            if next_rx == next_bx and next_ry == next_by:  # 빨간 구슬과 파란 구슬이 동시에 같은 칸에 있을 수 없다.
                if r_count > b_count:  # 이동 거리가 많은 구슬을 한칸 뒤로
                    next_rx -= dx[i]
                    next_ry -= dy[i]
                else:
                    next_bx -= dx[i]
                    next_by -= dy[i]
            # BFS 탐색을 마치고, 방문 여부 확인
            if not visited[next_rx][next_ry][next_bx][next_by]:
                visited[next_rx][next_ry][next_bx][next_by] = True
                q.append((next_rx, next_ry, next_bx, next_by, depth + 1))
    print(0)  # 실패


bfs()

타인의 코드~ 설명이 가장 잘써있어서 가져왔다.