백준 새로운 게임2 [17837] 파이썬(Python) 코드 + 해설

백준 17837 새로운 게임2 문제

문제 설명

재현이는 체스판과 말을 이용하여 새로운 게임을 만들었다. 이 게임은 크기가 N×N인 체스판에서 진행되며, 말은 총 K개가 사용된다. 말은 원판 모양이며, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색(0), 빨간색(1), 파란색(2) 중 하나로 색칠되어 있다.

게임은 체스판 위에 말을 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 오른쪽(1), 왼쪽(2), 위쪽(3), 아래쪽(4) 중 하나이다.

각 턴은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때, 그 말 위에 다른 말이 있으면 함께 이동한다. 말의 이동 규칙은 다음과 같다.

1. 이동하려는 칸이 흰색인 경우:
   • 그 칸으로 이동한다.
   • 이동하려는 칸에 말이 이미 있는 경우, 이동하는 말들을 그 위에 쌓는다.
2. 이동하려는 칸이 빨간색인 경우:
   • 이동한 후에 이동하는 말들의 순서를 반대로 바꾼다.
   • 이동하려는 칸에 말이 이미 있는 경우, 이동한 말들을 그 위에 쌓는다.
3. 이동하려는 칸이 파란색이거나 체스판을 벗어나는 경우:
   • 말의 이동 방향을 반대로 바꾸고 한 칸 이동한다.
   • 방향을 반대로 바꾼 후에도 이동하려는 칸이 파란색이거나 체스판을 벗어나면 이동하지 않고 가만히 있는다.

게임은 말이 4개 이상 쌓이는 순간 종료되며, 그 턴의 번호를 출력한다. 만약 1000턴이 넘도록 게임이 종료되지 않으면 -1을 출력한다.

문제 접근

이 문제는 시뮬레이션 문제로, 주어진 규칙에 따라 게임을 구현해야 한다. 말들의 위치와 스택 상태를 관리하면서, 매 턴마다 말들을 이동시키고, 말이 4개 이상 쌓이는지 확인해야 한다.

구현 방법

1. 데이터 구조 설계

• 체스판(board): 크기 N×N의 2차원 배열로, 각 칸에 말들의 번호를 리스트로 저장한다. 말들은 아래에서 위로 쌓이므로, 리스트의 앞쪽이 아래쪽 말이다.
• 말 정보(pieces): 각 말의 위치와 방향을 저장하는 리스트로 관리한다.
  • 말 번호에 해당하는 인덱스에 (x,y,dir)를 저장한다.
• 방향 벡터(dx, dy):
  • 방향은 1부터 4까지 주어지므로, 인덱스를 0부터 3까지로 조정한다.
  • 오른쪽(0): dx=0, dy=1
  • 왼쪽(1): dx=0, dy=-1
  • 위쪽(2): dx=-1, dy=0
  • 아래쪽(3): dx=1, dy=0

2. 이동 구현

• 각 턴마다 1번 말부터 K번 말까지 순서대로 이동한다.
• 말의 현재 위치와 방향을 가져온다.
• 해당 위치에서 말이 쌓여있는 스택에서 현재 말이 있는 인덱스를 찾는다.
• 그 말 위에 쌓인 말들도 함께 이동하므로, 스택에서 해당 인덱스부터 끝까지의 말들을 가져온다.
• 현재 위치의 스택에서 이동할 말들을 제거한다.
• 다음 위치를 계산한다.
  • 이동 방향에 따라 nx=x+dx[dir], ny=y+dy[dir]로 계산한다.
• 이동하려는 칸이 체스판을 벗어나거나 파란색인 경우:
  • 말의 방향을 반대로 바꾸고, 이동 방향을 다시 계산한다.
  • 다시 이동하려는 칸이 체스판을 벗어나거나 파란색이면 이동하지 않고 제자리로 돌아간다.
• 이동하려는 칸이 흰색인 경우:
  • 말들을 이동하여 그 칸의 스택에 그대로 쌓는다.
• 이동하려는 칸이 빨간색인 경우:
  • 말들의 순서를 반대로 바꾸고, 그 칸의 스택에 쌓는다.
• 이동한 말들의 위치 정보를 업데이트한다.
• 이동 후에 해당 칸에 쌓인 말의 개수가 4개 이상이면 게임을 종료한다.

3. 종료 조건 및 출력

• 게임은 최대 1000턴까지 진행한다.
• 말이 4개 이상 쌓이는 순간 게임을 종료하고, 해당 턴 번호를 출력한다.
• 1000턴이 넘도록 게임이 종료되지 않으면 -1을 출력한다.

 

백준 17837 새로운 게임 2 파이썬(Python) 정답 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
color = [list(map(int, input().split())) for _ in range(N)]

# 방향 설정: 오른쪽(0), 왼쪽(1), 위쪽(2), 아래쪽(3)
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

# 말 정보: 각 말의 위치(x, y), 방향(dir)
pieces = [0] * K
# 체스판: 각 칸에 쌓여있는 말들의 번호를 리스트로 저장
board = [[[] for _ in range(N)] for _ in range(N)]

for i in range(K):
    x, y, dir = map(int, input().split())
    pieces[i] = [x - 1, y - 1, dir - 1]
    board[x - 1][y - 1].append(i)

def reverse_dir(dir):
    if dir == 0:
        return 1
    elif dir == 1:
        return 0
    elif dir == 2:
        return 3
    elif dir == 3:
        return 2

turn = 0
game_over = False

while turn <= 1000 and not game_over:
    turn += 1
    for i in range(K):
        x, y, dir = pieces[i]
        idx = board[x][y].index(i)
        move_pieces = board[x][y][idx:]
        board[x][y] = board[x][y][:idx]
        nx = x + dx[dir]
        ny = y + dy[dir]

        # 이동하려는 칸이 체스판을 벗어나거나 파란색인 경우
        if not (0 <= nx < N and 0 <= ny < N) or color[nx][ny] == 2:
            dir = reverse_dir(dir)
            pieces[i][2] = dir
            nx = x + dx[dir]
            ny = y + dy[dir]
            if not (0 <= nx < N and 0 <= ny < N) or color[nx][ny] == 2:
                # 이동하지 않고 제자리로 돌아감
                board[x][y].extend(move_pieces)
                continue

        # 흰색인 경우
        if color[nx][ny] == 0:
            board[nx][ny].extend(move_pieces)
        # 빨간색인 경우
        elif color[nx][ny] == 1:
            board[nx][ny].extend(move_pieces[::-1])

        # 말들의 위치 업데이트
        for num in move_pieces:
            pieces[num][0] = nx
            pieces[num][1] = ny

        # 말이 4개 이상 쌓이면 게임 종료
        if len(board[nx][ny]) >= 4:
            game_over = True
            break

if turn > 1000:
    print(-1)
else:
    print(turn)

백준 17837 새로운 게임 2 코드 해설

• 입력 처리:
  • 체스판의 색상 정보를 color 리스트에 저장한다.
  • 각 말의 위치와 방향을 pieces 리스트에 저장한다.
  • 체스판의 각 칸에 말들의 번호를 board 리스트에 저장한다.
• reverse_dir 함수:
  • 이동 방향을 반대로 바꿔주는 함수이다.
• 메인 루프:
  • turn 변수를 증가시키며 게임을 진행한다.
  • 각 턴마다 1번 말부터 K번 말까지 순서대로 이동시킨다.
  • 말의 이동 규칙에 따라 이동을 구현한다.
  • 이동 후에 말이 4개 이상 쌓이면 게임을 종료한다.
• 출력:
  • 게임이 종료된 턴 번호를 출력한다.
  • 1000턴을 초과하면 -1을 출력한다.

백준 17837 새로운 게임 2 제출 결과

백준 17837 새로운 게임 2 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.