[BOJ] 17837 - 새로운 게임 2 (Python)

 

 

아이디어

 

조건에 따라 말을 이동시키며 이동한 칸의 말 개수가 4개 이상인 경우 해당 턴을 출력한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(0, 1), (0, -1), (-1, 0), (1, 0)]

def solution():

    def reverse(idx):
        bottom = idx
        while idx != -1:
            bottom = idx
            pieces[idx][3], pieces[idx][4] = pieces[idx][4], pieces[idx][3]
            idx = pieces[idx][4]
        return bottom

    def move(color):
        top, bottom = board[r][c], i
        board[r][c] = pieces[i][4]
        if pieces[i][4] != -1:
            pieces[pieces[i][4]][3] = -1
            pieces[i][4] = -1
        if color == 1:
            top, bottom = i, reverse(i)
        if board[nr][nc] != -1:
            pieces[board[nr][nc]][3] = bottom
            pieces[bottom][4] = board[nr][nc]
        board[nr][nc] = top
        idx = bottom
        while idx != -1:
            pieces[idx][0], pieces[idx][1] = nr, nc
            idx = pieces[idx][3]

    N, K = map(int, input().split())
    board_color = [tuple(map(int, input().split())) for _ in range(N)]
    board = [[-1]*N for _ in range(N)]
    pieces = []
    for i in range(K):
        r, c, d = map(int, input().split())
        pieces.append([r-1, c-1, d-1, -1, -1])
        board[r-1][c-1] = i
    for t in range(1, 1001):
        for i in range(K):
            r, c, d, child, parent = pieces[i]
            dr, dc = delta[d]
            nr, nc = r+dr, c+dc
            if nr >= N or nr < 0 or nc >= N or nc < 0 or board_color[nr][nc] == 2:
                if pieces[i][2]%2:
                    pieces[i][2] -= 1
                else:
                    pieces[i][2] += 1
                d = pieces[i][2]
                dr, dc = delta[d]
                nr, nc = r+dr, c+dc
                if N > nr >= 0 and N > nc >= 0 and board_color[nr][nc] != 2:
                    move(board_color[nr][nc])
            else:
                move(board_color[nr][nc])
            cnt = 1
            child, parent = pieces[i][3], pieces[i][4]
            while child != -1:
                cnt += 1
                child = pieces[child][3]
            while parent != -1:
                cnt += 1
                parent = pieces[parent][4]
            if cnt >= 4:
                print(t)
                return
    print(-1)

solution()