[백준 17780번] 파이썬 - 새로운 게임

백준 17780 - 새로운 게임

시간 제한 0.5초, 메모리 제한 512MB

# 조건

• 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다.
• 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다.
• 말은 원판 모양이고, 하나의 말 위에 다른 말을 올릴 수 있다.
• 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.
• 게임은 체스판 위에 말 K개를 놓고 시작한다.
  • 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다.
  • 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.
• 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다.
• 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동하며, 가장 아래에 있는 말만 이동할 수 있다.
• 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다.
• 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.
• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다.
  • 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다.
  • 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
• 다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

• 첫 번째 턴은 아래와 같이 진행된다.

• 두 번째 턴은 아래와 같이 진행

• 체스 판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 떄, 게임이 종료되는 턴의 번호를 구해보자.

입력

• 첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다.
• 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다.
• 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다.
  • 0은 흰색, 1은 빨간색, 2는 파란색이다.
• 다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다.
• 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다.
• 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.
• 같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

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

제한

• 4 ≤ N ≤ 12
• 4 ≤ K ≤ 10

# 접근 방법

• 우선 반대 방향으로 변경해주기 편하게 이동 방향을 오른쪽, 위쪽, 왼쪽, 아래쪽으로 변경해준다.
  • 따라서 입력 받을 때, 2인경우 3으로, 3인 경우 2로 변경해준다.
• 체스판의 상태를 알려줄 arr 리스트, 체스말의 번호와 위치를 기록해둘 chess 리스트, 체스말의 번호 : (위치, 방향)을 기록할 info 딕셔너리를 사용해준다.
• 여기서 중요한 점은 이동시키는 말 아래에 다른 말이 있는 경우 현재 말의 차례는 지나쳐주어야 한다.
• 각각의 색깔별로 함수를 나누어서 구현하였다.
  • white인 경우, 앞에서 부터 pop 하여 이동할 칸에 누적
  • red 인 경우, 뒤에서부터 pop하여 이동할 칸에 누적
  • blue 인 경우, +2 % 4를 통하여 방향을 변경해주고 이동하는 칸의 색깔에 따라서 로직 수행해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def move(num):  
    si, sj, d = info[num]  
    if len(chess[si][sj]) > 1:  
        val = chess[si][sj][0]  
        si, sj, d = info[val]  
        if num != val:  
            return 0  
    else:  
        val = num  

    # 범위 체크해주기  
    # 벗어난다면 파란색    
    ni, nj = si+di[d], sj+dj[d]  
    if 0<= ni < N and 0<= nj < N:  
        # 흰색이라면 이동시키고 위에 올려준다.  
        if arr[ni][nj] == 0:  
            white(si, sj, ni, nj)  
            if len(chess[ni][nj]) > 3:  
                return 1  

        # 빨간색이라면 말의 순서를 변경해준다.  
        elif arr[ni][nj] == 1:  
            red(si, sj, ni, nj)  
            if len(chess[ni][nj]) > 3:  
                return 1  

        # 파란색인 경우  
        # 방향 반대로 해주고 그래도 파란색이면 정지        # 파란색이 아닌 경우 한 칸 이동        
        elif arr[ni][nj] == 2:  
            ri, rj = blue(si, sj, d, val)  
            if len(chess[ri][rj]) > 3:  
                return 1  
    else:  
        ri, rj = blue(si, sj, d, val)  
        if len(chess[ri][rj]) > 3:  
            return 1  

    return 0  


def white(si, sj, ni, nj):  
    while chess[si][sj]:  
        temp = chess[si][sj].pop(0)  
        td = info[temp][2]  
        info[temp] = [ni, nj, td]  
        chess[ni][nj].append(temp)  

def red(si, sj, ni, nj):  
    while chess[si][sj]:  
        temp = chess[si][sj].pop()  
        td = info[temp][2]  
        info[temp] = [ni, nj, td]  
        chess[ni][nj].append(temp)  

def blue(si, sj, d, val):  
    d = (d + 2) % 4  
    ni, nj = si + di[d], sj + dj[d]  
    info[val] = [si, sj, d]  
    if 0 <= ni < N and 0 <= nj < N:  
        if arr[ni][nj] == 1:  
            red(si, sj, ni, nj)  
        elif arr[ni][nj] == 0:  
            white(si, sj, ni, nj)  

        return (ni, nj)  
    else:  
        return (si, sj)  

N, K = map(int, input().split())  
# 체스판 정보  
arr = [[*map(int, input().split())] for _ in range(N)]  
# 체스 말의 정보  
chess = [[[] for _ in range(N)]  for _ in range(N)]  
info = dict()  
# 오른쪽, 위쪽, 왼쪽, 아래쪽  
di, dj = [0, -1, 0, 1], [1, 0, -1, 0]  

for i in range(1, K+1):  
    a, b, c = map(int, input().split())  
    if c == 2:  
        c = 3  
    elif c == 3:  
        c = 2  
    chess[a-1][b-1].append(i)  
    info[i] = [a-1, b-1, c-1]  

cnt = 0  
flag = True  
while cnt < 1000 and flag:  
    cnt += 1  
    # 이번 턴에 이동한 말을 체크해주는 리스트  
    for i in range(1, K+1):  
        result = move(i)  
        if result:  
            print(cnt)  
            flag = False  
            break  
if cnt > 999:  
    print(-1)