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

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

13460번: 구슬 탈출 2

 

구슬이 겹쳤을 때가 관건인 문제였다.(이거 고민하느라 오래걸려서...)

BFS는 둘째치고 시뮬레이션 너무 복잡한 것 같다.

삼성 SW 역량 테스트 문제라는데ㅋㅋㅋㅋ... 어려웠다ㅜ

from collections import deque
n,m = map(int,input().split())

board = [list(map(str, input())) for _ in range(n)]


# 구슬 위치 체크
for i in range(n):
    for j in range(m):
        if board[i][j] == "B":
            x1,y1 = i,j
            board[i][j] = "."
        elif board[i][j] == "R":
            x2,y2 = i,j
            board[i][j] = "."



dxs = [1,-1,0,0]
dys = [0,0,-1,1]


def move(x, y, dx, dy):
    nx, ny = x, y
    cnt = 0
    while True:
        if board[nx+dx][ny+dy] != '#' and board[nx+dx][ny+dy] != 'O':
            nx += dx
            ny += dy
            cnt += 1
        else:
            break
    return nx, ny, cnt

    

q = deque()
# 파란 구슬, 빨간구슬 위치 저장
q.append((x1,y1,x2,y2,0))

def bfs():
    while q:    
        x1,y1,x2,y2, cnt = q.popleft()
        if cnt > 10:
            continue

        for dx,dy in zip(dxs,dys):
            nx1,ny1,cnt1 = move(x1,y1,dx,dy)        
            nx2,ny2,cnt2 = move(x2,y2,dx,dy)        
            

            if board[nx1+dx][ny1+dy] == 'O':
                continue
            if board[nx2+dx][ny2+dy] == 'O' and cnt < 10:
                return cnt+1

            if nx1 == nx2 and ny1 == ny2:
                if cnt2 > cnt1:
                    nx2 -= dx
                    ny2 -= dy
                else:
                    nx1 -= dx
                    ny1 -= dy
            if x1 == nx1 and y1 == ny1 and x2 == nx2 and y2 == ny2:
                continue
            q.append((nx1, ny1, nx2, ny2, cnt+1))
            
    return -1

print(bfs())