[백준 13460] 구슬 탈출 2 ❗❗❗

코뉴·2022년 2월 6일

백준🍳

목록 보기

96/149

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

🥚문제

🥚입력/출력

🍳코드

import sys
from collections import deque
input = sys.stdin.readline

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 = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def find(str):
    # str의 좌표 찾기
    for r in range(N):
        for c in range(M):
            if board[r][c] == str:
                return (r, c)
    return None


def move(x, y, dx, dy):
    # 이동 횟수
    steps = 0
    while board[x][y] != 'O' and board[x+dx][y+dy] != '#':
        x += dx
        y += dy
        steps += 1
    return x, y, steps


def bfs(rx, ry, bx, by):
    cnt = 1
    q = deque([(rx, ry, bx, by, cnt)])
    visited[rx][ry][bx][by] = True

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

        # 10번 이하로 움직여서 빨간 구슬을 빼낼 수 없다
        if cnt > 10:
            break

        for i in range(4):
            new_rx, new_ry, r_steps = move(rx, ry, dx[i], dy[i])
            new_bx, new_by, b_steps = move(bx, by, dx[i], dy[i])

            # (new_bx, new_by)가 구멍이 아니면 (실패 조건 만족 X)
            if board[new_bx][new_by] != 'O':
                # (new_rx, new_ry)가 구멍이라면 (성공 조건 만족 O)
                if board[new_rx][new_ry] == 'O':
                    print(cnt)
                    return

                # 기울인 후 빨간 구슬과 파란 구슬이 같은 위치에 있다면
                if new_rx == new_bx and new_ry == new_by:
                    # steps가 적은 것이 더 먼저 도착.
                    # steps가 더 큰 색의 구슬을 dx dy만큼 움직이기 이전 위치로 되돌려놓음
                    if r_steps < b_steps:
                        new_bx -= dx[i]
                        new_by -= dy[i]
                    else:
                        new_rx -= dx[i]
                        new_ry -= dy[i]

                # (new_rx, new_ry), (new_bx, new_by) 를 동시에 방문한 적이 없다면
                if not visited[new_rx][new_ry][new_bx][new_by]:
                    visited[new_rx][new_ry][new_bx][new_by] = True
                    q.append((new_rx, new_ry, new_bx, new_by, cnt + 1))

    # 실패
    print(-1)


r_x, r_y = find('R')
b_x, b_y = find('B')


bfs(r_x, r_y, b_x, b_y)

🧂아이디어

구현, 탐색

매우 도움을 받았던 글들 : https://wlstyql.tistory.com/72 , https://rebas.kr/724

find(str)

str에 넣은 문자열의 board 상에서의 위치를 리턴한다.
빨간 구슬, 파란 구슬의 좌표를 구하는 데 사용한다.

move(x, y, dx, dy)

(x, y) 위치에 있는 구슬을 (dx, dy)방향 -상/하/좌/우- 으로 굴리는 동작을 한다.
처음 입력으로 받은 (x, y) 위치에서 더이상 굴러갈 수 없을 때까지의 이동횟수를 steps에 저장한다.
현재 위치가 구멍('O')이 아니고, 다음에 움직일 위치가 벽('#')이 아닐 때까지 x를 dx만큼, y를 dy만큼 움직인 뒤, steps를 증가시킨다.
x, y, steps를 리턴한다.

bfs(rx, ry, bx, by)

빨간 구슬의 좌표 rx, ry와 파란 구슬의 좌표 bx, by를 인자로 받는다.

cnt에 구슬을 굴린 횟수를 저장한다.

visited를 이용하여 방문을 표시한다.
- 이때, visited를 4차원 리스트로 만들어야 함에 유의한다!⭐⭐⭐⭐⭐
- (rx, ry)와 (bx, by) 모두 방문한 적이 있어야 중복된 상태이다.
- (rx, ry)나 (bx, by) 둘 중 하나만 방문한 적이 있고, 하나는 새로 방문했다면 이는 새로운 상태이다.
- 이를 확인하기 위해 4차원 리스트를 사용해야 한다.

while loop 내부 설명
- 10번 이하로 움직여서 빨간 구슬을 빼낼 수 없다면 while문을 빠져나간 뒤 -1을 출력한다.
- cnt가 아직 10 이하라면 상, 하, 좌, 우 방향으로 굴리는 경우를 테스트한다.
- dx[i], dy[i] 방향으로 움직인 결과를 move함수를 사용하여 빨간 구슬, 파란 구슬 각각에 대해 구한다.
- 파란 구슬을 움직인 결과 도달하는 (new_bx, new_by)가 구멍이 아니라면 실패 조건이 아니므로 아래 과정을 실행한다.
  - 빨간 구슬을 움직인 결과 도달하는 (new_rx, new_ry)가 구멍이라면 성공 조건이므로 지금까지의 cnt를 출력하고 종료한다.
  - (new_rx, new_ry)가 구멍이 아니라면, 아래 과정을 실행한다.
    - (new_rx, new_ry)와 (new_bx, new_by)가 같은 위치에 있다면 움직인 횟수인 r_steps와 b_steps를 비교한다. 움직인 횟수가 적은 것이 더 먼저 도착하므로 값이 더 큰 색의 구슬을 dx[i], dy[i]만큼 움직이기 전 위치로 되돌린다. ⭐⭐⭐⭐⭐
    - (new_rx, new_ry)와 (new_bx, new_by)를 동시에 방문한 적이 없다면 새로운 상태이므로, visited에 표시하고 q에 삽입한다.