백준 17837번) 새로운 게임2 - 파이썬

새로운 게임2

 문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 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로 한시간 정도 고민해서 풀었다. ㅜ_ㅜ

 

고려해야할 것은 각각의 숫자가 움직이는 곳의 색깔, 파란색 일시 한칸 더 움직이는 것, 1000 이상이면 없는 것으로 판단하는 것

움직일 곳이 파란색 이나 벽일 때 direction이 변경 되므로 고려해준다. 

 

크게 attach_red, attach_blue, attach_white, go_forward로 함수를 작성해주어 재사용 해주는 식으로 진행하였다.

return 값이 나올 수 있게 함수로 사용해주면 용이하다. 

 

 

 코드

# https://www.acmicpc.net/problem/17837

from collections import deque

N, K = map(int, input().split())

# 말이 4개 이상 쌓이는 순간 게임이 종료된다.

# 1 : →, 2: ←, 3: ↑, 4: ↓
board = []
direct_dic = {}

for i in range(N):
    board.append(list(map(int, input().split())))

stack_board = [[[] for _ in range(N)] for _ in range(N)]

queue = deque([])

for i in range(K):
    X, Y, dir = map(int, input().split())
    X -= 1
    Y -= 1
    queue.append([X,Y])
    direct_dic[i+1] = dir
    stack_board[X][Y].append(i+1)

def attach_blue(cnt_val, cnt_number, go_stack, remain_stack):
    cnt_X, cnt_Y = cnt_val
    
    cnt_dir = direct_dic[cnt_number]
    
    if cnt_dir == 1:
        cnt_dir = 2
    elif cnt_dir == 2:
        cnt_dir = 1
    elif cnt_dir == 3:
        cnt_dir = 4
    else:
        cnt_dir = 3
    
    direct_dic[cnt_number] = cnt_dir
    
    nxt_X = cnt_X
    nxt_Y = cnt_Y
    
    if cnt_dir == 1: # 오른쪽이라면
        nxt_Y += 1
    elif cnt_dir == 2: # 왼쪽이라면
        nxt_Y -= 1
    elif cnt_dir == 3: # 위쪽이라면
        nxt_X -= 1
    else:
        nxt_X += 1
    
    if nxt_X < 0 or nxt_Y < 0 or nxt_X >= N or nxt_Y >= N: # 벽이라면
        return cnt_X, cnt_Y
    
    if board[nxt_X][nxt_Y] == 2: # 파란색 이라면
        return cnt_X, cnt_Y
    elif board[nxt_X][nxt_Y] == 0:
        attach_white([cnt_X, cnt_Y], [nxt_X, nxt_Y], go_stack, remain_stack)
        return nxt_X, nxt_Y
    elif board[nxt_X][nxt_Y] == 1:
        attach_red([cnt_X, cnt_Y], [nxt_X, nxt_Y], go_stack, remain_stack)    
        return nxt_X, nxt_Y
    

def attach_red(cnt_val, nxt_val, go_stack, remain_stack):
    # 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    cnt_X, cnt_Y = cnt_val
    nxt_X, nxt_Y = nxt_val
    
    go_stack.reverse()
    
    stack_board[cnt_X][cnt_Y] = remain_stack
    stack_board[nxt_X][nxt_Y].extend(go_stack)
    

def attach_white(cnt_val, nxt_val, go_stack, remain_stack):
    cnt_X, cnt_Y = cnt_val
    nxt_X, nxt_Y = nxt_val
    
    stack_board[cnt_X][cnt_Y] = remain_stack
    stack_board[nxt_X][nxt_Y].extend(go_stack)

def go_forward(cnt_X, cnt_Y, direction):
    global N
    
    nxt_X = cnt_X
    nxt_Y = cnt_Y
    
    if direction == 1: # 오른쪽이라면
        nxt_Y += 1
    elif direction == 2: # 왼쪽이라면
        nxt_Y -= 1
    elif direction == 3: # 위쪽
        nxt_X -= 1
    else:
        nxt_X += 1
    
    if nxt_X < 0 or nxt_Y < 0 or nxt_X >= N or nxt_Y >= N:
        return False, cnt_X, cnt_Y
    elif board[nxt_X][nxt_Y] == 2:
        return False, cnt_X, cnt_Y
    else:
        return True, nxt_X, nxt_Y

def solution(cnt, queue):
    while cnt < 1000:
        
        cnt_number = 1
        
        for idx in range(len(queue)):
            cnt_X, cnt_Y = queue[idx]
            cnt_dir = direct_dic[cnt_number]
            cnt_stack = stack_board[cnt_X][cnt_Y]
            
            val_idx = cnt_stack.index(cnt_number)
            
            remain_stack = cnt_stack[:val_idx] # 남아야 하는 스택
            go_stack = cnt_stack[val_idx:] # 옮겨져야 하는 스택
            
            is_bool, nxt_X, nxt_Y = go_forward(cnt_X, cnt_Y, cnt_dir) # 첫 번째는 벽인지 아닌지 판단 가능,
            
            if is_bool == False: # 벽이나 파란색이라면 ?
                nxt_X, nxt_Y = attach_blue([cnt_X, cnt_Y], cnt_number, go_stack, remain_stack) # 파란색과 똑같음
            else:
                nxt_color = board[nxt_X][nxt_Y]
                if nxt_color == 0: # 흰색이면
                    attach_white([cnt_X, cnt_Y], [nxt_X, nxt_Y], go_stack, remain_stack)
                elif nxt_color == 1: # 빨간색이면
                    attach_red([cnt_X, cnt_Y], [nxt_X, nxt_Y], go_stack, remain_stack)
            
            for val in go_stack:
                queue[val-1] = [nxt_X, nxt_Y]
                
            if len(stack_board[nxt_X][nxt_Y]) >= 4:
                return cnt
            
            cnt_number += 1
        
        cnt += 1
        
    return -1
        
print(solution(1,queue))