[백준 / python] 17780: 새로운 게임

문제

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

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.

다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.

풀이

구현 문제

import sys
from collections import deque

dirs = ((0, 0), (0, 1), (0, -1), (-1, 0), (1, 0))
N, K = map(int, sys.stdin.readline().split())
board_info = [[2] * (N + 2) for _ in range(N + 2)]
board = [[0] * (N + 2) for _ in range(N + 2)]
total_queue = [deque([n]) for n in range(K + 1)]
queue_pos = [(0, 0)]
unit_queue, unit_dir = [0], [0]

for r in range(N):
    row = map(int, sys.stdin.readline().strip().split())
    for c, v in enumerate(row):
        board_info[r + 1][c + 1] = v

for i in range(1, K + 1):
    r, c, d = map(int, sys.stdin.readline().split())
    queue_pos.append((r, c))
    unit_dir.append(d)
    unit_queue.append(i)
    board[r][c] = i

# 말 쌓기. 만약 말이 4 개이상 쌓인다면 출력 후 프로그램 종료
def move_units(frm, to, reverse=False):
    cur = total_queue[frm]
    nxt = total_queue[to]
    if len(cur) + len(nxt) >= 4:
        print(attempt)
        exit()
    while cur:
        unit = cur.popleft() if not reverse else cur.pop()
        unit_queue[unit] = to
        nxt.append(unit)

def move_unit(unit):
    cur_queue_index = unit_queue[unit]
    cur_r, cur_c = queue_pos[cur_queue_index]

    if total_queue[cur_queue_index][0] != unit:
        return

    new_r, new_c = cur_r + dirs[unit_dir[unit]][0], cur_c + dirs[unit_dir[unit]][1]
    cur_queue = board[cur_r][cur_c]
    other_queue = board[new_r][new_c]

    if board_info[new_r][new_c] == 0:  # 흰색
        board[cur_r][cur_c] = 0
        if other_queue != 0:
            move_units(cur_queue, other_queue)
            return
        board[new_r][new_c] = cur_queue
        queue_pos[cur_queue] = (new_r, new_c)

    elif board_info[new_r][new_c] == 1:  # 빨간색
        board[cur_r][cur_c] = 0
        if other_queue != 0:
            move_units(cur_queue, other_queue, True)
            return
        total_queue[cur_queue].reverse()
        board[new_r][new_c] = cur_queue
        queue_pos[cur_queue] = (new_r, new_c)

    elif board_info[new_r][new_c] == 2:  # 파란색
        new_dir = unit_dir[unit] + 1 if unit_dir[unit] % 2 == 1 else unit_dir[unit] - 1
        new_r, new_c = cur_r + dirs[new_dir][0], cur_c + dirs[new_dir][1]
        unit_dir[unit] = new_dir
        if board_info[new_r][new_c] == 2:
            return
        move_unit(unit)

attempt = 1
while attempt <= 1000:
    for i in range(1, K + 1):
        move_unit(i)
    attempt += 1
print(-1)