[TIL] 2023-09-07 코테 (구현 1문제)

골드1. 백준 13460 구슬 탈출 2

풀이

그렇게까지 복잡한 구현이 아니라고 생각했는데 시간이 너무 오래 걸려서 해설을 봤다ㅠ 참고한 블로그는 여기

포인트
1. 공은 동시에 굴러감
2. 같은 방향으로 다 굴린 다음 같은 좌표에 존재한다면 더 많이 움직인 구슬을 한칸 뒤로
3. 공은 벽을 만날 때까지 계속 데굴데굴 굴러감
4. 움직인 좌표값의 저장은 최종적으로 도착한 좌표만 해도 OK (빨간 공, 파란 공 좌표를 동시에 저장)

큐에 값을 넣을 때 (빨간공 좌표, 파란공 좌표) 를 같이 넣어서 동시에 계산해줘야 한다. 그리고 벽을 만날 때까지 계속 굴리다가 벽을 만나면 한칸 뒤로 후진해줘야 한다. 만약 구멍을 만난다면 끝! 10번 넘게 움직이거나 BFS를 다 돌았음에도 도달하지 못했다면 -1를 출력한다.

코드를 보면 대충 이제 알겠는데 시간 안에 차근차근 구현하는건 아직도 왜 이리 부족한지 모르겠다. 정진하자!!!!!

코드

from sys import stdin
from collections import deque

input = stdin.readline

# 목표는 빨간 구슬 구멍으로 빼내기 / 파란 구슬이 들어가면 안됨!
# 공은 동시에 움직인다.
# n = 세로 크기 Row, m = 가로 크기 Col
n, m = map(int, input().split(" "))

# . = 빈칸 / # = 장애물, 벽 / o = 구멍
# 그래프 입력받기
graph = []
R = [0, 0]
B = [0, 0]
target = [0, 0]
for a in range(n):
    sub = list(input())
    graph.append(sub)
    for b in range(m):
        if sub[b] == "R":
            R = [a, b]
        elif sub[b] == "B":
            B = [a, b]
        elif sub[b] == "O":
            target = [a, b]

answer_mark = False

# 상, 하, 좌, 우
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

q = deque()

# R 좌표, B 좌표
q.append((R[0], R[1], B[0], B[1], 0))

visited = set()
visited.add((R[0], R[1], B[0], B[1]))

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

    if graph[rx][ry] == "O":
        print(cnt)
        answer_mark = True
        break

    if cnt >= 10:
        continue

    # r, b 움직이기
    for k in range(4):
        r_move = 0
        b_move = 0

        # r 움직이기
        nrx = rx + dx[k]
        nry = ry + dy[k]

        while True:
            # 벽이면 한칸 뒤로 이동
            if graph[nrx][nry] == "#":
                nrx -= dx[k]
                nry -= dy[k]
                break
            elif graph[nrx][nry] == "O":
                break

            nrx += dx[k]
            nry += dy[k]

            r_move += 1

        # b 움직이기
        nbx = bx + dx[k]
        nby = by + dy[k]
        while True:
            # 벽이면 한칸 뒤로 이동
            if graph[nbx][nby] == "#":
                nbx -= dx[k]
                nby -= dy[k]
                break
            elif graph[nbx][nby] == "O":
                break

            nbx += dx[k]
            nby += dy[k]
            b_move += 1

        # B 빠지면 안됨
        if graph[nbx][nby] == "O":
            continue

        # r, b가 같은 경우 / O일때 아닐때
        if nrx == nbx and nry == nby:
            # 더 움직임이 많은걸 한칸 뒤로
            if r_move > b_move:
                nrx -= dx[k]
                nry -= dy[k]
            else:
                nbx -= dx[k]
                nby -= dy[k]

        if not (nrx, nry, nbx, nby) in visited:
            visited.add((nrx, nry, nbx, nby))
            q.append((nrx, nry, nbx, nby, cnt + 1))


if answer_mark == False:
    print(-1)