[BOJ] 17837. 새로운 게임2 (🥇, 시뮬레이션)

🔗

풀이

1. 1 ~ K 까지 차례대로 수행한다.
2. 이동할 때 위에 쌓여있는 블럭들은 함께 이동한다.
3. 빨간색일 때는 뒤집어야 한다.
4. 이동할 수 없는 곳이거나 파란색 칸인 경우에는 방향을 바꿔서 다시 움직인다.
5. 어느 한 칸이라도 4개 이상의 블럭이 쌓이면 종료되어야 한다
6. 함께 이동하게 되는 모든 블럭들에 대해서 이동할 때마다 새로운 위치를 기록한다.

매번 번호 순서대로 이동해야 하기 때문에 각 번호의 현재 위치, 방향이 기록되어야 한다. 여기서 블럭이 쌓이는 것은 1차원 배열로 나타내며 0번 인덱스가 가장 아래가 된다. 위에 쌓이는 블럭들은 함께 이동한다고 했으므로 해당 번호가 위치해 있는 곳에서 몇번째 위치에 쌓여있는지에 대한 정보도 함께 기록해야 한다. 해당 칸에서 해당 번호의 인덱스 역시 함께 기록한다. 번호별로 행, 열, 방향, 인덱스가 기록할 수 있도록 딕셔너리를 사용했다.

블럭은 번호 순서대로 움직이며 함께 이동하는 블럭들도 위치가 변경된다. 변경되는 위치에 대해서는 매번 새로 기록해주어야 한다. 때문에 함께 이동한 블럭들에 대해서 매번 모두 위치를 업데이트 한다.

파란색 칸은 경계선 밖의 칸과 같은 취급을 한다. 처음 만났을 때는 방향만 변경해서 다시 이동하게 하지만, 두 번째 만나게 되면 움직이지 않는다 이 부분을 no_recur 변수를 사용하여 구현하였다. 이 값이 True 일 때 파란색 칸이나 경계선 밖의 칸을 마주하게 되면 움직이지 않는다.

어떤 한 칸이라도 4칸 이상의 블럭이 쌓이게 되면 is_finish 변수를 True 로 변경하고 곧바로 종료한다.

# 새로운 게임 2

def move(nr, nc, tmp):
    global arr, is_finish
    start_h = len(arr[nr][nc])
    arr[nr][nc].extend(tmp)
    if len(arr[nr][nc]) >= 4:
        is_finish = True
    for new_h, x in enumerate(tmp, start_h):
        piece[x] = [nr, nc, piece[x][2], new_h]

def judge(i, no_recur=False):
    global piece, arr
    r, c, d, h = piece[i]

    nr = r + DIR[d][0]
    nc = c + DIR[d][1]

    if not(0 <= nr < N and 0 <= nc < N) or (CHESS[nr][nc] == 2 and not no_recur):
        piece[i][2] = DIR_REVERSE[d]
        judge(i, True)
        return 
    
    tmp = arr[r][c][h:]
    arr[r][c] = arr[r][c][:h]
    if CHESS[nr][nc] == 1:
        tmp.reverse()

    if CHESS[nr][nc] == 2 and no_recur:
        nr, nc = r, c
    
    move(nr, nc, tmp)

def game():
    global arr, piece
    for i in range(1, K+1):
        judge(i)
        if is_finish:
            return 

N, K = map(int, input().split())
CHESS = [list(map(int, input().split())) for _ in range(N)]
DIR = ((0, 1), (0, -1), (-1, 0), (1, 0))
DIR_REVERSE = [1, 0, 3, 2]
piece = dict()
arr = [[[] for _ in range(N)] for _ in range(N)]
is_finish = False

for i in range(1, K+1):
    r, c, d = map(int, input().split())
    piece[i] = [r-1, c-1, d-1, 0] # 행, 열, 방향, 쌓여 있는 위치
    arr[r-1][c-1].extend([i])

turn = 0
while turn <= 1000:
    game()
    turn += 1
    if is_finish:
        break
        
if turn == 1001:
    turn = -1
print(turn)