[ 백준 17837 ] 새로운 게임 2

문제 보기

구현, 시뮬레이션 문제이다.

턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료되며, 게임이 종료되는 턴의 번호를 출력하면 된다.

 

A번 말이 이동하려는 칸은 흰색, 빨간색, 파란색, 체스판을 벗어나는 경우 중에 하나이다. 체스판을 벗어나는 경우는 파란색과 동일하기 때문에 총 3가지 경우가 존재한다. 따라서 3가지 연산을 구현하면 된다.

 

말의 이동을 관리하기 위해서 2차원 배열을 선언하였다. 만약 해당 칸에 말이 없다면 빈 공간 형태이며, 말이 2마리 있다면 첫 번째 말, 두 번째 말 순서로 쌓인 형태이다.

 

흰색과 빨간색 칸 연산은 매우 유사하며 말을 쌓는 순서만 바꾸면 된다. 전체적인 연산 순서는 아래와 같다.

1. 현재 칸에서 이동하려는 말의 인덱스를 파악한다. (현재 칸에 A, B, C, D, E 말이 있으며 C 말을 이동하려는 상황이라고 가정)

2. 흰색 칸 - C, D, E 순서로 쌓아야 한다.

 -> C부터 배열의 끝까지 읽으면서 append 연산으로 이동하려는 칸에 삽입

  빨간색 칸 - E, D, C 순서로 쌓아야 한다.

 -> 배열의 끝부터 C까지 거꾸로 읽으면서 append 연산으로 이동하려는 칸에 삽입

 

파란색 칸 연산은 아래 순서로 진행한다.

1. 현재 말의 이동 방향을 반대로 한다.

2. 한 칸 이동한다. (이동하려는 칸이 파란색 혹은 체스판을 벗어나는 경우 가만히 있는다.)

 - 이동하려는 칸이 흰색 혹은 빨간색 칸이면 위에서 구현한 함수 사용

파란색 연산은 방향 전환과 흰색, 빨간색 연산을 합친 연산이라고 볼 수 있다.

 

아래는 흰색, 빨간색, 파란색, 방향 전환, 말 4마리 확인하는 함수 총 6가지를 구현한 코드이다.

 

코드 

def change_direction(d):
    if d == 1:
        return 2
    elif d == 2:
        return 1
    elif d == 3:
        return 4
    elif d == 4:
        return 3


def red_operation(key, pre_r, pre_c, post_r, post_c, chess, horse):
    if len(chess[pre_r][pre_c]) == 1:
        horse[key] = (post_r, post_c, horse[key][2])
        chess[post_r][post_c].append(chess[pre_r][pre_c][0])
        chess[pre_r][pre_c] = []
    else:
        index = chess[pre_r][pre_c].index(key)
        for i in range(len(chess[pre_r][pre_c]) - 1, index - 1, - 1):
            chess[post_r][post_c].append(chess[pre_r][pre_c][i])
            horse[chess[pre_r][pre_c][i]] = (post_r, post_c, horse[chess[pre_r][pre_c][i]][2])
        chess[pre_r][pre_c] = chess[pre_r][pre_c][:index]


def white_operation(key, pre_r, pre_c, post_r, post_c, chess, horse):
    if len(chess[pre_r][pre_c]) == 1:
        horse[key] = (post_r, post_c, horse[key][2])
        chess[post_r][post_c].append(chess[pre_r][pre_c][0])
        chess[pre_r][pre_c] = []
    else:
        index = chess[pre_r][pre_c].index(key)
        for i in range(index, len(chess[pre_r][pre_c])):
            chess[post_r][post_c].append(chess[pre_r][pre_c][i])
            horse[chess[pre_r][pre_c][i]] = (post_r, post_c, horse[chess[pre_r][pre_c][i]][2])
        chess[pre_r][pre_c] = chess[pre_r][pre_c][:index]


def blue_operation(key, chess, horse):
    r, c, d = horse[key]
    d = change_direction(d)
    horse[key] = (r, c, d)
    if d == 1:
        if c + 1 == n:
            return
        elif maps[r][c + 1] == 2:
            return
        else:  # 이동 가능
            if maps[r][c + 1] == 0:
                white_operation(key, r, c, r, c + 1, chess, horse)
            elif maps[r][c + 1] == 1:
                red_operation(key, r, c, r, c + 1, chess, horse)
    elif d == 2:
        if c - 1 < 0:
            return
        elif maps[r][c - 1] == 2:
            return
        else:
            if maps[r][c - 1] == 0:
                white_operation(key, r, c, r, c - 1, chess, horse)
            elif maps[r][c - 1] == 1:
                red_operation(key, r, c, r, c - 1, chess, horse)
    elif d == 3:
        if r - 1 < 0:
            return
        elif maps[r - 1][c] == 2:
            return
        else:
            if maps[r - 1][c] == 0:
                white_operation(key, r, c, r - 1, c, chess, horse)
            elif maps[r - 1][c] == 1:
                red_operation(key, r, c, r - 1, c, chess, horse)
    else:
        if r + 1 == n:
            return
        elif maps[r + 1][c] == 2:
            return
        else:
            if maps[r + 1][c] == 0:
                white_operation(key, r, c, r + 1, c, chess, horse)
            elif maps[r + 1][c] == 1:
                red_operation(key, r, c, r + 1, c, chess, horse)


def check(array):
    for i in range(n):
        for j in range(n):
            if len(array[i][j]) >= 4:
                return True
    return False


if __name__ == "__main__":
    n, k = map(int, input().split())  # 체스판의 크기, 말의 개수
    maps = [list(map(int, input().split())) for _ in range(n)]
    chess = [[[] for _ in range(n)] for _ in range(n)]
    horse = {}
    for i in range(1, k + 1):
        r, c, d = map(int, input().split())
        horse[i] = (r - 1, c - 1, d)
        chess[r - 1][c - 1].append(i)

    time = 0
    flag = True
    while time <= 1000 and flag:
        for key in horse.keys():  # 각 말들 이동 수행
            r, c, d = horse[key]

            if d == 1:  # 오른쪽
                if c + 1 < n:
                    if maps[r][c + 1] == 0:
                        white_operation(key, r, c, r, c + 1, chess, horse)
                    elif maps[r][c + 1] == 1:
                        red_operation(key, r, c, r, c + 1, chess, horse)
                    elif maps[r][c + 1] == 2:
                        blue_operation(key, chess, horse)
                else:
                    blue_operation(key, chess, horse)
                if (c + 1 < n and len(chess[r][c + 1]) >= 4) or (c - 1 >= 0 and len(chess[r][c - 1]) >= 4):
                    flag = False
                    break
            elif d == 2:  # 왼쪽
                if c - 1 >= 0:
                    if maps[r][c - 1] == 0:
                        white_operation(key, r, c, r, c - 1, chess, horse)
                    elif maps[r][c - 1] == 1:
                        red_operation(key, r, c, r, c - 1, chess, horse)
                    elif maps[r][c - 1] == 2:
                        blue_operation(key, chess, horse)
                else:
                    blue_operation(key, chess, horse)
                if (c + 1 < n and len(chess[r][c + 1]) >= 4) or (c - 1 >= 0 and len(chess[r][c - 1]) >= 4):
                    flag = False
                    break
            elif d == 3:  # 상
                if r - 1 >= 0:
                    if maps[r - 1][c] == 0:
                        white_operation(key, r, c, r - 1, c, chess, horse)
                    elif maps[r - 1][c] == 1:
                        red_operation(key, r, c, r - 1, c, chess, horse)
                    elif maps[r - 1][c] == 2:
                        blue_operation(key, chess, horse)
                else:
                    blue_operation(key, chess, horse)
                if (r + 1 < n and len(chess[r + 1][c]) >= 4) or (r - 1 >= 0 and len(chess[r - 1][c]) >= 4):
                    flag = False
                    break
            else:  # 하
                if r + 1 < n:
                    if maps[r + 1][c] == 0:
                        white_operation(key, r, c, r + 1, c, chess, horse)
                    elif maps[r + 1][c] == 1:
                        red_operation(key, r, c, r + 1, c, chess, horse)
                    elif maps[r + 1][c] == 2:
                        blue_operation(key, chess, horse)
                else:
                    blue_operation(key, chess, horse)
                if (r + 1 < n and len(chess[r + 1][c]) >= 4) or (r - 1 >= 0 and len(chess[r - 1][c]) >= 4):
                    flag = False
                    break
        time += 1

    # 출력
    if time > 1000:
        print(-1)
    else:
        print(time)