[Python] 백준 13460: 구슬 탈출 2

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

풀이

  • 4방향 모두 순회하면서 가능한 포지션과 움직인 횟수를 체크
  • 한 번 기울일 때 파란 구슬이 빠지는 경우 바로 다음 방법으로 넘어가기
  • 빨간 구슬이 구멍으로 빠지면 cnt 넘겨주기
  • 이미 방문한 곳은 visited로 체크해서 중복 없게 하기
  • 구슬 위치가 같아질 경우 이전 위치와 더 많이 차이나는 구슬을 뒤에 배치

코드

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

n, m = map(int, input().split())
maps = []
r_position = [0, 0]
b_position = [0, 0]
for i in range(n):
    temp = [x for x in input().rstrip()]
    if 'R' in temp:
        r_position = [temp.index('R'), i]

    if 'B' in temp:
        b_position = [temp.index('B'), i]
    maps.append(temp)

#0: 왼쪽, 1: 오른쪽, 2: 위, 3:아래
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 1
q = deque()
q.append((cnt, r_position, b_position))

maps[r_position[1]import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
maps = []
rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
    temp = [x for x in input().rstrip()]
    if 'R' in temp:
        rx, ry = temp.index('R'), i

    if 'B' in temp:
        bx, by = temp.index('B'), i
    maps.append(temp)

#0: 왼쪽, 1: 오른쪽, 2: 위, 3:아래
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 1
q = deque()
q.append([cnt, rx, ry, bx, by])

maps[ry][rx] = "."
maps[by][bx] = "."
visited = [[rx,ry,bx,by]]

def tilt():
    while q:
        cnt, rx, ry, bx, by = q.popleft()
        for i in range(4):
            r_nx, r_ny = rx, ry
            b_nx, b_ny = bx, by
            # 파란 구슬 이동
            while maps[b_ny + dy[i]][b_nx + dx[i]] == ".":
                b_nx += dx[i]
                b_ny += dy[i]
            # 파란 구슬이 빠질경우 다음 케이스로 넘어가기
            if maps[b_ny + dy[i]][b_nx + dx[i]] == "O":
                continue
            # 빨간 구슬 이동
            while maps[r_ny + dy[i]][r_nx + dx[i]] == ".":
                r_nx += dx[i]
                r_ny += dy[i]
            if maps[r_ny + dy[i]][r_nx + dx[i]] == "O":
                return cnt
            else:
                if r_nx == b_nx and r_ny == b_ny:  # 같은 위치일 경우 더 많이 움직인 구슬을 뒤에
                    if abs(rx - r_nx) + abs(ry - r_ny) > abs(bx - b_nx) + abs(by - b_ny):
                        r_nx = r_nx - dx[i]
                        r_ny = r_ny - dy[i]
                    else:
                        b_nx = b_nx - dx[i]
                        b_ny = b_ny - dy[i]
                if [r_nx, r_ny, b_nx, b_ny] not in visited:
                    q.append((cnt + 1, r_nx, r_ny, b_nx, b_ny))
                    visited.append([r_nx, r_ny, b_nx, b_ny])
        if cnt > 10:
            return -1
    return -1
print(tilt())

질문에 있는 반례 다 넘어가는데 어디가 틀렸는지 모르겠다....ㅎ ㅏ..
3시간 넘게 걸려서 풀었는데 맞추지도 못하고 .. 착찹하다

부호를...>=에서 >로 바꾸니까 통과했다. 너무 허무하다..ㅠㅠ 정신차리자

좋은 웹페이지 즐겨찾기