백준 17837 - 새로운 게임2(골드 2, 시뮬레이션, 구현)

Seop·2023년 9월 25일

알고리즘

목록 보기

15/16

문제

새로운 게임 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

정답 - Python3

import sys
dxs, dys = (1, 0, -1, 0), (0, 1, 0, -1)
convert_d = {1: 0, 2: 2, 3: 3, 4: 1}

n, k = map(int, sys.stdin.readline().rstrip().split())
g = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
board = [[[] for _ in range(n)] for __ in range(n)]
corrd = {}
for i in range(k):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())  # a - 1 > y, b - 1 > x
    board[a - 1][b - 1].append(i + 1)
    corrd[i + 1] = [b - 1, a - 1, convert_d[c]]


def in_range(x, y):
    return 0 <= x < n and 0 <= y < n


def move():
    for t in range(1, k + 1):
        x, y, d = corrd[t]
        order = board[y][x].index(t)
        moving = board[y][x][order:]
        stay = board[y][x][:order]
        nx, ny = x + dxs[d], y + dys[d]

        if not in_range(nx, ny) or (in_range(nx, ny) and g[ny][nx] == 2):
            d = (d + 2) % 4
            nx, ny = x + dxs[d], y + dys[d]
            corrd[t] = [x, y, d]

        if in_range(nx, ny) and (g[ny][nx] == 1 or g[ny][nx] == 0):
            if g[ny][nx] == 0:
                board[ny][nx].extend(moving)
            else:
                board[ny][nx].extend(list(reversed(moving)))
            board[y][x] = stay
            for m in moving:
                ox, oy, od = corrd[m]
                corrd[m] = [nx, ny, od]
            if len(board[ny][nx]) >= 4:
                return True
    return False


cnt = 1
while cnt < 1001:
    if move():
        break
    cnt += 1
print(cnt if cnt < 1001 else -1)

결과

풀이

정말 귀찮고, 삼성코테스러운 문제입니다ㅠㅠ
하지만 차근차근 문제의 조건을 맞춰가다 보면 생각보다는(?) 수월하게 풀 수 있는 문제입니다!

저는 우선 문제의 변수들을 제 멋대로 커스텀 했습니다.

1. 방향 변경

기존에는

1	2	3	4
→	←	↑	↓

였다면 저는

0	1	2	3
→	↓	←	↑

로 변경했습니다.
그 이유는 dxs, dys를 사용할 때 현재 방향 d 에서 +2를 하면 반대 방향으로 바꾸기 원활하게 하기 위함이죠!
격자 밖으로 벗어나거나, 파란색 칸을 만날 경우에 반대 방향으로 바꿔줘야 하므로 제가 편한대로 바꿨습니다

2. 좌표 변경

체스 기물들의 좌표를 r, c의 형식으로 기존에는 줬습니다.
하지만 저는 그렇게 x, y 좌표의 형식으로 보는게 더 익숙해서 r - 1 = y, c - 1 = x 로 변경해서 작업했습니다.

그리고 문제를풀기 위해서 다음과 같은 자료 구조들을 사용했습니다.

g : 격자의 상황을 기억하기 위한 2차원 리스트, 처음 값을 받기만 하고 변경되지 않는다. 체스 기물을 옮길 때, 조회만 실시한다
board : 현재 체스 판의 기물들의 상태를 확인하는 3차원 리스트. x, y 좌표에 알맞은 기물들을 쌓아서 관리하기 위해서 3차원으로 선언함
corrd: 기물들의 번호, 현재 좌표, 진행 방향을 관리하는 dictionary. 기물을 옮길 경우 board의 값만 변경하는 것이 아니라, corrd에 저장된 변수도 최신화를 시켜줘야한다!!

그리고 실질적으로 기물을 옮겨주는 move 가 존재합니다
함수 내부는 다음과 같은 순서로 설계했습니다.

1 ~ k 번 기물까지 동일한 아래의 작업(옮기기)을 거친다.

t번 기물의 현재 좌표, 방향을 가져온다.
t번 기물의 현재 위치에서 기물의 순서를 가져온다
list slicing을 통해서 옮겨질 기물들(moving), 현재 좌표에 남을 기물들(stay)를 나눈다
다음 좌표 (nx, ny)를 구한다
1. 만약 (nx, ny)가 격자 밖을 벗어나거나, 파란색 칸일 경우 방향을 반대로 바꾼다
2. nx, ny를 다시 초기화 해주고 바뀐 방향을 corrd에 최신화해준다
만약 (nx, ny)가 격자 내에 있고, 파란색이 아닐 경우 다음과 같은 작업을 실시한다
- 움직인 칸이 흰색 칸일 경우(g[ny][nx] == 0) board[ny][nx] 에 moving을 쌓는다
- 움직인 칸이 빨간색 칸일 경우(g[ny][nx] == 1) board[ny][nx] 에 뒤집어진 moving을 쌓는다
  다음 칸에 쌓았으니, moving안의 기물들의 변경된 좌표를 corrd에서 최신화해준다.
- 만약 쌓여진 칸에 4개 이상의 기물이 있을 경우(len(board[ny][nx] >= 4)), True를 return 한다(중단 조건)