[Algorithm] BaekJoon : 17837. 새로운 게임 2 by Python

[문제 바로가기] 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

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

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

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

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

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

제한

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

💡 문제 풀이

주어진 문제를 그대로 구현하면 해결되는 문제다.

문제의 관건은 체스판 위의 말들이 이동시 다른 말 위에 올라가거나 혹은 내려갈 수 있기 때문에 '어떤 자료구조를 사용하여 말의 이동을 표현하냐'였다.

체스판의 크기가 최대 12x12이고 메모리 제한이 512MB로 충분하여 말의 위치와 체스판 위의 이동을 분리하여 진행하였다.

말의 위치는 딕셔너리를 이용하여 '말 번호 : 좌표'의 형태로 값을 입력했다.

체스판 위의 이동은 3차원 배열을 이용하였고 특정 좌표에 다수의 말이 쌓이게 되면 해당 좌표의 배열에 들어온 말의 번호를 순서대로 추가하였다.

step 1)
변수 선언
location : 체스판 위의 이동을 알려주는 3차원 배열
horses : 현재 말의 위치를 알려주는 딕셔너리 - '말 번호 : 좌표'
answer : 게임 진행 '턴'의 값을 담을 변수

step 2)
모든 말이 순서대로 1번씩 이동하게되면 1턴이기 때문에 반복문을 이용하여 1턴을 마치면 answer+1을 해주었다.

말의 이동을 위해 solve함수를 만들었다.
horses[말의 번호]를 이용하여 움직이려는 좌표를 계산한다.

만약) 새로운 좌표가 체스판 범위 안에 들어오면 2가지 경우로 나눈다.

• 움직이려는 칸이 흰색, 빨간색인 경우
• 움직이려는 칸이 파란색인 경우

만약) 새로운 좌표가 체스판 범위 안에 들어오지 않으면

• 파란색과 같은 경우이므로 blue 함수를 실행한다.

흰색과 빨간색을 white_red 함수 하나로 만든 이유는 빨간색칸에 이동하면 말의 순서만 바뀔뿐 다른 작업은 흰색과 동일하기 때문이다.

step 3)
움직이려는 칸이 흰색, 빨간색인 경우 → white_red 함수

location에서 움직이려는 말의 번호를 찾는다.(이후의 말들을 가져오기 위한 작업)

찾았으면 슬라이싱을 이용하여 이후의 말들을 움직이려는 칸의 배열에 합친다.

• 흰색의 경우 순서 그대로 합친다.
• 빨간색의 경우 앞뒤 순서를 바꿔 합친다.

옮긴 후 이동 전의 칸에는 슬라이싱을 이용하여 옮긴 말들을 없앤다.

step 4)
말을 이동시키면서 4개 이상의 말이 쌓이면 즉시 진행을 멈춘다. → is_finish 함수

이동 시킨 좌표(nr, nc)의 배열의 길이가 4이상이면 answer 출력 후 exit() 함수를 이용하여 프로그램을 종료시켰다.

4이상이 아니면 새로 옮긴 말들의 좌표를 갱신해준다.

step 5)
solve 함수에서 이동하려는 좌표가 체스판 범위를 벗어나거나 파란색인 경우에는 blue 함수를 실행한다.

blue함수에서 우선 방향을 바꿔주었다.
좌(1) ↔ 우(2) / 상(3) ↔ 하(4)를 바꿔주면 되기 때문에 홀수이면 +1 짝수이면 -1을 하여 방향을 바꾸었다.

바꾼 방향으로 1칸 이동을 진행한다.
만약) 이동하려는 칸이 흰색 또는 빨간색이면 white_red 함수를 실행한다.

이동하려는 칸이 체스판을 벗어나거나 파란색이면 방향만 바꾸어주면 되는데 blue함수에서 방향을 이미 바꾸었기 때문에 더 이상 진행할 내용은 없다.

코드는 다음과 같다.

import sys
dir = [(0, 0), (0, 1), (0, -1), (-1, 0), (1, 0)]
N, K = map(int, input().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def is_finish(nr, nc):
    if len(location[nr][nc]) >= 4:
        print(answer)
        exit()

def white_red(r, c, nr, nc, num, color):
    for idx in range(len(location[r][c])):
        if location[r][c][idx] == num:
            if color == "white": location[nr][nc] += location[r][c][idx:]
            else: location[nr][nc] += location[r][c][idx:][::-1]
            location[r][c] = location[r][c][:idx]
            break
    is_finish(nr, nc) # 4개의 말이 쌓였는지 확인
    for horse in location[nr][nc]:
        horses[horse][0], horses[horse][1] = nr, nc

def blue(r, c, d, num):
    if d % 2: d += 1
    else: d -= 1
    horses[num][2] = d
    nr = r + dir[d][0]
    nc = c + dir[d][1]
    if 0 <= nr < N and 0 <= nc < N:
        if not matrix[nr][nc]: white_red(r, c, nr, nc, num, "white") # 흰색
        elif matrix[nr][nc] == 1: white_red(r, c, nr, nc, num, "red") # 빨간색

def solve(num):
    r, c, d = horses[num]
    nr = r + dir[d][0]
    nc = c + dir[d][1]
    if 0 <= nr < N and 0 <= nc < N:
        if not matrix[nr][nc]: # 흰색
            white_red(r, c, nr, nc, num, "white")
        elif matrix[nr][nc] == 1: # 빨간색
            white_red(r, c, nr, nc, num, "red")
        else: # 파란색
            blue(r, c, d, num)
    else:
        blue(r, c, d, num)

location = [[[] for _ in range(N)] for _ in range(N)]
horses = dict()
for idx in range(K):
    r, c, d = map(int, input().split())
    location[r-1][c-1].append(idx)
    horses[idx] = [r-1, c-1, d]

answer = 1
while answer < 1000:
    for num in range(K):
        solve(num)
    answer += 1
print(-1)