[BaekJoon] 백준 13460번 구슬 탈출 2

[BaekJoon] 백준 13460번 구슬 탈출 2

 

문제: www.acmicpc.net/problem/13460

 

내코드

 

- bfs 문제

- 지금까지 풀었던 bfs 문제들과 비슷하지만 구슬 두개를 움직여야 한다는 점에서 생각이 필요했다.

- 마지막에 계속 막히던 부분(백준 68%.. 정도에서 틀림)이 있었는데 횟수의 문제였다. if point[2] > 10을 if point[2] > 9 로 바꿔주니까 통과함

 

from collections import deque

arr = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())


# 지도 정보 저장
def init():
    for i in range(n):
        tmp = list(str(input()))
        if "R" in tmp:
            red = [i, tmp.index("R")]
        if "B" in tmp:
            blue = [i, tmp.index("B")]
        arr.append(tmp)
    return red, blue


def move(point, i):
    num = 0
    new_point = point
    # 한칸씩 이동해서 이동한 칸이 벽이면 이동 못하니까 멈추고, 이동한 칸이 구멍이면 구멍에 빠지게 되니까 이동을 멈춤
    while arr[new_point[0] + dx[i]][new_point[1] + dy[i]] != "#" and arr[new_point[0]][new_point[1]] != "O":
        new_point = [new_point[0] + dx[i], new_point[1] + dy[i]]
        num += 1
    return new_point, num


def main(red, blue):
    # 방문 안한 칸이면 0, 방문시 1
    visited = [[[[0] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
    visited[red[0]][red[1]][blue[0]][blue[1]] = 1

    # 구슬 처음 위치 넣기, 빨간 구슬/파란 구슬/이동 횟수
    queue = deque()
    queue.append([red, blue, 0])

    while queue:
        point = queue.popleft()
        # 10회 이하로 안되면 -1 출력 후 종료
        if point[2] > 9:
            print(-1)
            return

        # 상하좌우에 대해서 구슬 이동
        for i in range(4):
            red_new, red_num = move(point[0], i)
            blue_new, blue_num = move(point[1], i)

            # 만약 파란색 구슬이 구멍에 빠졌으면 안되니까 이 경우는 버림
            if arr[blue_new[0]][blue_new[1]] == "O":
                continue
            # 만약 위에 파란색 구슬이 빠진 경우에 안걸렸는데 빨간색 구슬이 빠진 경우가 생기면 횟수 + 1 (이번에 움직인 것) 출력 후 종료
            if arr[red_new[0]][red_new[1]] == "O":
                print(point[2] + 1)
                return

            # 이동했는데 두 구슬의 위치가 같은 경우
            if red_new == blue_new:
                # 이동 횟수 비교해서 해당 위치에 더 멀었던 구슬의 위치를 이동시켜줌
                if red_num > blue_num:
                    red_new = [red_new[0] - dx[i], red_new[1] - dy[i]]
                elif red_num <= blue_num:
                    blue_new = [blue_new[0] - dx[i], blue_new[1] - dy[i]]

            # 두 구슬의 위치가 방문하지 않았던 위치라면 큐에 푸시
            if visited[red_new[0]][red_new[1]][blue_new[0]][blue_new[1]] == 0:
                visited[red_new[0]][red_new[1]][blue_new[0]][blue_new[1]] = 1
                queue.append([red_new, blue_new, point[2] + 1])
    print(-1)


red_position, blue_position = init()
main(red_position, blue_position)

 

 

- 211018 다시 품

# BaekJoon13460.py
from collections import deque


N, M = map(int, input().split())
R = [0, 0]
B = [0, 0]
hole = [0, 0]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
board = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
    tmp = list(input())
    for j in range(M):
        board[i][j] = tmp[j]
        if tmp[j] == 'R':
            R = [i, j]
            board[i][j] = "."
        elif tmp[j] == 'B':
            B = [i, j]
            board[i][j] = "."
        elif tmp[j] == 'O':
            hole = [i, j]


# direction으로 빨간 구슬과 파란 구슬 옮기고 각자 위치 반환
def move(r, b, direction):
    global hole, board

    red = r[0] * direction[0] + r[1] * direction[1]
    blue = b[0] * direction[0] + b[1] * direction[1]
    marbles = []
    is_finished = [False, False]

    # 빨간 구슬이 파란 구슬보다 앞에 있다면
    if red >= blue:
        marbles.append(r)
        marbles.append(b)
    else:
        marbles.append(b)
        marbles.append(r)
    # 순서대로 이동
    while True:
        for i in range(2):
            if is_finished[i]:
                continue
            tr = [marbles[i][0] + direction[0], marbles[i][1] + direction[1]]
            # 구멍이 있으면 -1
            if tr == hole:
                marbles[i] = [-1, -1]
                is_finished[i] = True
            # 벽이거나 다른 구슬이 있으면 멈춤
            elif board[tr[0]][tr[1]] == "#" or tr == marbles[1 - i]:
                is_finished[i] = True
            # 아무것도 없으면 계속 한칸씩 이동
            else:
                marbles[i] = [tr[0], tr[1]]
        # 두 구슬 다 움직일 수 없다면 종료
        if is_finished[0] and is_finished[1]:
            break

    if red >= blue:
        return marbles
    else:
        return [marbles[1], marbles[0]]


def bfs():
    global N, M, board, R, B, dx, dy

    queue = deque([[R, B, 0]])  # 빨간 구슬 위치, 파란 구슬 위치, 움직인 횟수

    while queue:
        r, b, n = queue.popleft()

        # 10번 넘으면 제외
        if n >= 10:
            continue

        # 4방향으로 이동
        for i in range(4):
            nr, nb = move(r, b, [dx[i], dy[i]])
            # 더이상 구슬이 움직이지 않으면 continue
            if r == nr and b == nb:
                continue
            # 파란 구슬이 구멍에 빠지면 continue
            if nb[0] == -1:
                continue
            # 빨간 구슬만 구멍에 빠지면 정답
            elif nr[0] == -1:
                return n + 1
            # 어느 구슬도 구멍에 빠지지 않으면 append
            else:
                queue.append([nr, nb, n + 1])

    return -1



print(bfs())