문제 링크

17837 - 새로운 게임 2

문제 설명

N*N 크기의 체스판에 k개의 말이 있다. 체스판의 각 칸은 흰색 또는 빨간색 또는 파란색이다. 한 말 위에 다른 말을 올릴 수 있다.
초기 상태는 게임판 위에 k개의 말이 주어진 이동방향을 바라본다.
진행은 다음과 같다. 1번의 턴에
1번부터 k번 말까지 순서대로 이동한다. 말이 쌓여있으면 같이 이동하고 한칸에 4개 이상 쌓이면 종료한다.
-> A번 말이 이동하려는 칸이

1. 흰색칸
   : 해당 칸으로 이동한다.
   -> 이미 말이 있으면? 그 말 위에 A 말 올리기
   -> A말 위에 다른 말 있으면? 그대로 같이 움직인다.
   예를 들어, 현재 A가 있는 칸에 A-B-C 순으로 쌓여있고, 이동하려는 칸에 E-F-G 순으로 쌓여있으면, 이동 후에는 E-F-G-A-B-C가 된다.
2. 빨간색칸
   : 해당 칸으로 이동하고, A말과 위의 말들사이의 순서를 바꿔 쌓는다.
   예를 들어, 현재 A가 있는 칸에 A-B-C 순으로 쌓여있고, 이동하려는 칸에 E-F-G 순으로 쌓여있으면, 이동 후에는 E-F-G-C-B-A가 된다.
3. 파란색칸
   : A말의 이동 방향을 반대로 바꾸고 그 방향으로 이동한다. 이동하려는 칸이 또 파란색이거나 범위를 벗어나면 움직이지 않는다.
4. 이동 범위를 벗어나면 파란칸과 같이 동작한다.

체스판의 배열, 말들의 초기 위치와 방향이 주어졌을때 몇 turn만에 이동이 끝나는지 구하시오

문제 풀이

입력

board_color[i][j] : (i,j)칸의 색 저장 -> 0:흰색, 1:빨간색, 2:파란색
horses[i] : i번째 말의 [x행, y행, 방향]을 저장하는 dictionary
horse_on_board[i][j] : (i,j)칸에 쌓여있는 말들의 번호를 저장하는 인덱스 -> 인덱스가 작은게 밑에서부터 쌓여있음

N, k = map(int, input().split())
board_color = []
for _ in range(N):
    board_color.append(list(map(int, input().split())))
horses = defaultdict()
horse_on_board = [[[] for _ in range(N)] for _ in range(N)]
for i in range(k):
    x, y, d = map(int, input().split())
    horses[i] = [x-1, y-1, d]
    horse_on_board[x-1][y-1].append(i)

매 턴마다의 이동

모든 말들에 대해 다음에 이동할 칸을 구하고, 칸의 색에 맞는 동작을 수행한다.

count = 1
while True:
    flag = True
    if count > 1000:
        break
    for h in horses.keys():
        # 모든 말에 대해서 이동
        x, y, d = horses[h]
        nx, ny = x+dx[d], y+dy[d]

        if in_bound(nx, ny):
            if board_color[nx][ny] == 0:
                # 흰색이면
                if move_white(h) == False:
                    flag = False
                    break
            elif board_color[nx][ny] == 1:
                # 빨간색이면
                if move_red(h) == False:
                    flag = False
                    break
            else:
                # 파란색이면
                if move_blue(h) == False:
                    flag = False
                    break
        else:
            # 방향 바꾸고 한칸 이동
            if move_blue(h) == False:
                flag = False
                break
    if flag == False:
        break
    count += 1

흰칸으로의 이동

def move_white(h):
    x, y, d = horses[h]
    nx, ny = x+dx[d], y+dy[d]
    # (nx,ny)칸에서 현재 말의 인덱스 구하기
    idx = horse_on_board[x][y].index(h)
    
    # 4보다 크면 종료
    if len(horse_on_board[nx][ny]) + len(horse_on_board[x][y][idx:]) >= 4:
        return False
    
    # 현재말~ 위에 쌓여있는 말 이동시키기
    for moving in horse_on_board[x][y][idx:]:
        horses[moving][0] = nx
        horses[moving][1] = ny
    horse_on_board[nx][ny] += horse_on_board[x][y][idx:]
    horse_on_board[x][y] = horse_on_board[x][y][:idx]
    return True

빨간칸으로의 이동

흰칸에서의 수행과 동일하지만, 이동시 reversed 함수를 이용해서 순서를 뒤집어준다.

def move_red(h):
    x, y, d = horses[h]
    nx, ny = x+dx[d], y+dy[d]
    idx = horse_on_board[x][y].index(h)
    if len(horse_on_board[nx][ny]) + len(horse_on_board[x][y][idx:]) >= 4:
        return False
    for moving in horse_on_board[x][y][idx:]:
        horses[moving][0] = nx
        horses[moving][1] = ny
    horse_on_board[nx][ny] += list(reversed(horse_on_board[x][y][idx:]))
    horse_on_board[x][y] = horse_on_board[x][y][:idx]
    return True

파란칸으로의 이동

방향을 뒤집고 이동시킨다. 이동할 칸이 흰색, 빨간색인 각각의 경우에 맞는 함수를 호출

def move_blue(h):
    flag = True
    x, y, d = horses[h]
    # 방향 뒤집기
    horses[h][2] = reverse[d]
    nx, ny = x+dx[horses[h][2]], y+dy[horses[h][2]]
    if in_bound(nx, ny) and board_color[nx][ny] != 2:
        # 범위를 벗어나지 않고 파란 칸이 아니면
        if board_color[nx][ny] == 0:
            flag = move_white(h)
        else:
            flag = move_red(h)
    return flag

전체코드

import sys
from collections import defaultdict

dx = [0, 0, 0, -1, 1]
dy = [0, 1, -1, 0, 0]
reverse = {1:2, 2:1, 3:4, 4:3}
input = sys.stdin.readline

N, k = map(int, input().split())
board_color = []
for _ in range(N):
    board_color.append(list(map(int, input().split())))
horses = defaultdict()
horse_on_board = [[[] for _ in range(N)] for _ in range(N)]
for i in range(k):
    x, y, d = map(int, input().split())
    horses[i] = [x-1, y-1, d]
    horse_on_board[x-1][y-1].append(i)

def in_bound(x,y):
    if x in range(N) and y in range(N):
        return True
    return False

def move_white(h):
    x, y, d = horses[h]
    nx, ny = x+dx[d], y+dy[d]
    idx = horse_on_board[x][y].index(h)
    if len(horse_on_board[nx][ny]) + len(horse_on_board[x][y][idx:]) >= 4:
        return False
    for moving in horse_on_board[x][y][idx:]:
        horses[moving][0] = nx
        horses[moving][1] = ny
    horse_on_board[nx][ny] += horse_on_board[x][y][idx:]
    horse_on_board[x][y] = horse_on_board[x][y][:idx]
    return True

def move_red(h):
    x, y, d = horses[h]
    nx, ny = x+dx[d], y+dy[d]
    idx = horse_on_board[x][y].index(h)
    if len(horse_on_board[nx][ny]) + len(horse_on_board[x][y][idx:]) >= 4:
        return False
    for moving in horse_on_board[x][y][idx:]:
        horses[moving][0] = nx
        horses[moving][1] = ny
    horse_on_board[nx][ny] += list(reversed(horse_on_board[x][y][idx:]))
    horse_on_board[x][y] = horse_on_board[x][y][:idx]
    return True

def move_blue(h):
    flag = True
    x, y, d = horses[h]
    horses[h][2] = reverse[d]
    nx, ny = x+dx[horses[h][2]], y+dy[horses[h][2]]
    if in_bound(nx, ny) and board_color[nx][ny] != 2:
        # 범위를 벗어나지 않고 파란 칸이 아니면
        if board_color[nx][ny] == 0:
            flag = move_white(h)
        else:
            flag = move_red(h)
    return flag

count = 1
while True:
    flag = True
    if count > 1000:
        break
    for h in horses.keys():
        # 모든 말에 대해서 이동
        x, y, d = horses[h]
        nx, ny = x+dx[d], y+dy[d]

        if in_bound(nx, ny):
            if board_color[nx][ny] == 0:
                # 흰색이면
                if move_white(h) == False:
                    flag = False
                    break
            elif board_color[nx][ny] == 1:
                # 빨간색이면
                if move_red(h) == False:
                    flag = False
                    break
            else:
                # 파란색이면
                if move_blue(h) == False:
                    flag = False
                    break
        else:
            # 방향 바꾸고 한칸 이동
            if move_blue(h) == False:
                flag = False
                break
    if flag == False:
        break
    count += 1
if count > 1000:
    print(-1)
else:
    print(count)

소요 시간

1시간 30분
python의 슬라이싱이나 reversed같은 내장함수를 이용하면 쉽게 풀 수 있는 문제였는데,, 설계 맞게 해놓고 리스트 이름 햇갈려서 디버깅하는데 애먹음 ㄱ- 정신 췌리..