문제

BOJ 17780: 새로운 게임 https://www.acmicpc.net/problem/17780

풀이

조건

• 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다.
• 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다.
• 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.
• 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.
• 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다.
• 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동하며, 가장 아래에 있는 말만 이동할 수 있다.
• 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다.
  • 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
    • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
• 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.
• 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.
• 게임 종료 조건
  • 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.
  • 턴이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력

풀이 순서

• while문을 통해 시뮬레이션을 반복 수행한다.

  • 모든 말을 순서대로 이동시킨다.

    • 말이 장 밑에 깔려있는 말이면 방향에 맞춰 이동한다.
    • 다음 칸의 색깔을 확인하고 색깔 별 조건 대로 이동한다.

  • 1000번 이상 반복되면 종료한다.

  • 말이 4개 이상 겹쳐지면 종료한다.

• 조건과 기능을 함수로 만들면 쉽게 해결할 수 있다.

코드

Python

import sys

# _, 오른, 왼, 위, 아래
dx = [0, 0, 0, -1, 1]
dy = [0, 1, -1, 0, 0]

# 보드 크기, 말 개수
N, K = map(int, sys.stdin.readline().rstrip().split())
# 0: 흰, 1: 빨, 2: 파 -> 기록한 보드
board = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]

# 말 위치 기록(겹쳐진 말 포함)
record = [[[] for _ in range(N)] for _ in range(N)]

# 말 번호 별 위치, 방향 기록할 배열
horses_info = [[] for _ in range(K + 1)]
for i in range(1, K + 1):
    r, c, direction = map(int, sys.stdin.readline().rstrip().split())
    # 말 번호, 행, 열, 방향
    horses_info[i] = [i, r - 1, c - 1, direction]
    # 말 위치 기록(겹쳐지게)
    record[r - 1][c - 1].append(i)


# 가장 밑에 있는 말인지 확인하는 함수 (이동시키려는 말이 가장 밑에 있어야 이동시킬 수 있음)
def is_bottom_horse(h_num, x, y):
    horse_state = record[x][y]
    if horse_state[0] == h_num:
        return True
    else:
        return False


# 방향 반대로 바꾸는 함수
def reverse_dir(direction):
    if direction == 1:
        return 2
    elif direction == 2:
        return 1
    elif direction == 3:
        return 4
    elif direction == 4:
        return 3


# 파란색이거나 벗어난 칸이라서 반대로 이동해봤는데 또 그런 상태인지 확인하는 함수
def is_blue_again(x, y, direction):
    rev_dir = reverse_dir(direction)
    nnx = x + dx[rev_dir]
    nny = y + dy[rev_dir]

    if nnx < 0 or nny < 0 or nnx >= N or nny >= N or board[nnx][nny] == 2:
        return True
    return False


# 다음 칸으로 이동시키는 함수
def move_next_pos(x, y, direction):
    nx = x + dx[direction]
    ny = y + dy[direction]

    # 다음 칸이 판을 벗어나는 경우 or 파란칸
    if nx < 0 or ny < 0 or nx >= N or ny >= N or board[nx][ny] == 2:
        # 또 벗어나거나 파란칸이면 이동 안하고 방향만 반대로
        if is_blue_again(x, y, direction):
            return x, y, reverse_dir(direction)
        else:
            rev_dir = reverse_dir(direction)
            # 방향 바꿔서 이동한 칸의 색깔 별로 다시 처리해주기 위해 현재 함수 재귀 호출
            return move_next_pos(x, y, rev_dir)

    # 다음 칸이 빨강칸
    elif board[nx][ny] == 1:
        # 말 반대로 바꿔줌
        rev_horses = record[x][y][::-1]
        # 말들 차례로 다음 칸에 올림
        for value in rev_horses:
            record[nx][ny].append(value)
            # 말들 정보 갱신
            h_n, x, y, d = horses_info[value]
            horses_info[value] = [h_n, nx, ny, d]
        # 이전 칸에 있던 말을 모두 옮겼으므로 빈 칸으로 만들어 줌
        record[x][y] = []
    # 다음 칸이 흰칸
    elif board[nx][ny] == 0:
        # 말들 차례로 다음 칸에 올림
        for value in record[x][y]:
            record[nx][ny].append(value)
            # 말들 정보 갱신
            h_n, x, y, d = horses_info[value]
            horses_info[value] = [h_n, nx, ny, d]
        # 이전 칸에 있던 말을 모두 옮겼으므로 빈 칸으로 만들어 줌
        record[x][y] = []

    return nx, ny, direction


# 현재 턴에 모든 말들 이동시키는 함수
def move_all_horses():
    for horse in range(1, K + 1):
        horse_num, r, c, direction = horses_info[horse]
        # 말이 가장 밑이 아니면 다음 말로 넘어감
        if not is_bottom_horse(horse_num, r, c):
            continue

        # 현재 말 기준으로 옮기기 수행
        nx, ny, n_dir = move_next_pos(r, c, direction)
        # 현재 말 정보 갱신
        horses_info[horse_num] = [horse_num, nx, ny, n_dir]


# 게임이 끝날 수 있는지 확인하는 함수
def is_finish():
    for i in range(N):
        for j in range(N):
            if len(record[i][j]) >= 4:
                return True
    return False


# 게임 수행
answer = -1
time = 1
while time <= 1000:
    move_all_horses()

    if is_finish():
        answer = time
        break

    time += 1

print(answer)

정리

• 각 조건과 기능등을 함수로 쪼개 구현하니 생각보다 쉬웠다.