백준 문제 중 17837번, 구현, ‘새로운 게임2’

백준 문제 중 17837번

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

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다. ++ 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

입력

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

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

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

출력

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

---

풀이

문제 자체는 크게 어렵지 않았지만 체스말 하나하나 마다 동작을 봐야해서 디버깅 하는데 엄청 오랜 시간이 걸렸다.

코드의 구성은 다음과 같다.

1. 맵의 색을 입력받을 board, 체스말의 상태를 입력받을 pieces, 각 좌표마다 체스말이 쌓인 상태를 저장할 stacks를 선언하고, stacks를 pieces로 초기화 한다.
2. idx와 piece를 입력받아 체스말을 하나씩 움직이고 보드마다 쌓여 있는 말을 최신화 해줄 함수 move_piece(idx, piece)를 선언한다.
3. 턴마다 모든 체스말을 움직이고 턴이 1000이상이거나 체스말이 4개이상 쌓일경우 게임을 종료 하는 game_start()함수를 선언한다.
4. game_start()를 실행하고 return 값을 출력한다.

move_piece(idx, piece)를 좀 더 구체적으로 살펴보자.

1. 입력 받은 체스말이 이동할 다음 좌표 nr , nc의 색 board[nr][nc]가 2이면(파란색) 두가지 경우로 나눈다.
   • 바꾼 방향으로 이동 하려는데 파란색이거나 범위를 벗어난다면 pieces[idx]의 방향 성분인 pieces[idx][2]을 반대 방향으로 최신화 하고 num번째 체스말의 이동을 종료하고 False를 return 한다.(방향만 바뀌었으므로 쌓이는 상태에는 변화가 없음)
   • 바꾼 방향으로 이동이 흰색이나 빨간색이면 다음 좌표 nr, nc 를 반대 방향으로 한칸 진행한 좌표로 최신화한다.
2. 입력 받은 체스말이 이동할 다음 좌표 nr, nc 의 색 board[nr][nc] 2가 아니라면 deque로 선언한 tmp에 stacks[r][c]의 모든 값을 tmp[-1]과 체스말의 번호인 num이 같을때까지 꺼내서 저장한다.
3. tmp 안의 모든 체스말은 다음 좌표로 이동되므로 tmp안에 있는 모든 체스말의 좌표를 nr, nc로 최신화 해준다.
4. board[nr][nc]가 0 이라면 stacks[nr][nc]에 tmp를 pop으로 꺼내 넣고, board[nr][nc]가 1 이라면 stacks[nr][nc]에 tmp를 popleft로 꺼내 넣는다.
5. num번째 체스말의 이동이 종료 되고나면 stacks[nr][nc] >= 4 여부를 retrun 한다.

from pprint import pprint
from collections import deque

n, k = map(int, input().split())
 # 1행 1열부터 시작하는 board 선언, 범위를 벗어난경우는 2로 처리
board = [[2] * (n+2)] + [[2] + list(map(int,input().split())) + [2] for _ in range(n)] + [[2] * (n+2)]
pieces = [list(map(int ,input().split())) for _ in range(k)]

stacks = [[[] for _ in range(n+2)] for _ in range(n+2)]
 # stacks에 처음 체스말의 상태를 업데이트함
for idx, piece in enumerate(pieces):
    num = idx + 1
    r, c, d = piece
    stacks[r][c].append(num)

print('first')
for i in range(1, n+1):
    print(stacks[i][1:n+1])
print()



dir = {1: [0, 1], 2: [0, -1], 3: [-1, 0], 4: [1, 0]}
 # 반대 방향을 딕셔너리로 처리
reverse = {1: 2, 2: 1, 3: 4, 4: 3}

def move_piece(idx, piece):
    r, c, d = piece
    num = idx + 1
    nr, nc = r + dir[d][0], c + dir[d][1]
    print(f'num: {num} [r, c] to [nr, nc]: {[r, c]} to {[nr, nc]} color: {board[nr][nc]} dir: {d}')

     # 다음칸이 파란색이거나 범위를 벗어난 경우
    if board[nr][nc] == 2:
        d = reverse[d]
         # idx 체스말의 방향에 반대방향으로 최신화
        pieces[idx][2] = d
        nnr, nnc = r + dir[d][0], c + dir[d][1]
         # 반대 방향으로 이동하려는데 파란색이거나 범위를 벗어나면 종료
        if board[nnr][nnc] == 2:
            for i in range(1, n+1):
                print(stacks[i][1:n+1])
            return False
         # 다음으로 이동할 좌표를 최신화
        else:
            nr, nc = nnr, nnc
    
     # tmp에 stacks[r][c]에 있던 값들을 꺼내서  저장함.
    tmp = deque()
    while stacks[r][c]:
        tmp.append(stacks[r][c].pop())
        if tmp[-1] == num:
            break

     # tmp에 있는 값들의 좌표를 모두 최신화 해줌
    for stack_num in tmp:
        pieces[stack_num - 1][0], pieces[stack_num - 1][1] = nr, nc

     # board[nr][nc]이 0 이라면 순서대로 1이라면 역순으로 값을 넣어줌
    if board[nr][nc] == 0:
        while tmp:
            stacks[nr][nc].append(tmp.pop())
    elif board[nr][nc] == 1:
        while tmp:
            stacks[nr][nc].append(tmp.popleft())
    
    for i in range(1, n+1):
        print(stacks[i][1:n+1])

    return len(stacks[nr][nc]) >= 4




def game_start():
    turn = 1
    while turn <= 1000:
        print(f'turn: {turn}')
        for idx, piece in enumerate(pieces):
            if move_piece(idx, piece):
                return turn
        print()
        turn += 1
    else:
        return -1

print(game_start())

배운점

이 문제를 코딩테스트에서 만났다면 문제의 감은 잡히는데, 디버깅하는데 시간이 오래걸려서 아마도 풀지 못 했을듯 하다. 코드를 처음 구성할때 애초에 더 꼼꼼히 조건을 따지는 습관을 들여야겠다.