백준 1360번 구슬탈출 2 파이썬

문제

입력 , 출력


solution

import sys
from collections import deque


def bfsr():
    global res
    visited = [[[[0 for i in range(m)] for i in range(n)] for i in range(m)]
               for i in range(n)]
                   # 4차원 배열을 이용해서 visited를 만들어준다.
    while dq:
        rx, ry, bx, by, cnt = dq.popleft()
        visited[rx][ry][bx][by] = 1
        if cnt > 10:
            break
        for i in range(4):
            rnx, rny, cntr = move(rx, ry, dx[i], dy[i]) # 한쪽으로 기울여서 끝까지 보냄
            bnx, bny, cntb = move(bx, by, dx[i], dy[i]) # 한쪽으로 기울여서 끝까지 보냄
            if board[bnx][bny] == 'O': # 파란공이 먼저 빠지거나 , 같이 빠지면 안되기때문에 먼저 체크를 해준다
                continue
            elif board[rnx][rny] == 'O': # 파란공이 안바지고 빨간공이 빠지면 성공 출력후 끝
                print(cnt)
                return
            if rnx == bnx and rny == bny: # 이동이 더 많은 것을 뒤로빼줌
                if cntr < cntb:
                    bnx -= dx[i]
                    bny -= dy[i]
                else:
                    rnx -= dx[i]
                    rny -= dy[i]
            if visited[rnx][rny][bnx][bny] == 0: # 빨간공 , 파란공 위치를 방문한적이 없으면 dq에 삽입해주고 visited를 체크해준다.
                visited[rnx][rny][bnx][bny] = 1
                dq.append((rnx, rny, bnx, bny, cnt + 1))
    print(-1) # 출력을 못했으면 -1 실패


def move(x, y, nx, ny):
    cnt = 0
    while board[x + nx][y + ny] != '#' and board[x][y] != 'O':
    # '#'이 있는곳은 어차피 보드판을 벗어나지 않기때문에 0<=x+nx<n을 체크 안해줘도
    # 상관이 없으므로 그냥 '#'이 있는지 현재 O가 있는지 체크만 해주면 끝
    # O가 있으면 O위치에서 멈춰서 값을 리턴해준다.
    # O가 없고 #을 마주치면 거기서 값을 리턴해준다.
        cnt += 1
        x += nx
        y += ny
    return x, y, cnt


input = sys.stdin.readline
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
res = -1
n, m = map(int, input().split())
board = [['' for i in range(m)] for j in range(n)]
dq = deque()
x1, y1, x2, y2 = 0, 0, 0, 0
for i in range(n):
    a = input().strip()
    for j in range(m):
        if a[j] == 'B':
            x2 = i
            y2 = j
        if a[j] == 'R':
            x1 = i
            y1 = j
        board[i][j] = a[j]
dq.append((x1, y1, x2, y2, 1))
bfsr()

설명

키포인트

  1. 한쪽 방향으로 기울이면 끝까지 보내준다.
  2. 동시에 빠지면 실패
  3. 같은위치에 있는 경우면 이동을 덜 한것이 먼저 도착하므로 이동을 많이 한 공 위치를 뒤로 한칸 빼준다.

좋은 웹페이지 즐겨찾기