이번 문제는 삼성 기출 문제로 정말 어렵게 해결하였다. 처음에 데이터 관리 방식에 대해 고민을 많이 하였고, 해당 칸에 존재하는 체스말의 번호를 저장할 3차원 리스트와 각 말의 현재 위치와 방향을 저장할 리스트를 따로 관리하였다. 다음 칸이 0일 경우와 1일 경우에 대하여 0일 경우에는 현재 번호를 num으로 저장하여 num 위에 쌓인 체스말들을 함께 그 순서 그대로 다음 칸에 옮겼고, 1일 경우에는 현재 번호를 num으로 저장하여 num 위에 쌓인 체스말들을 함께 반대 순서로 다음 칸에 옮겼다. 그리고 2를 만날 경우에는 방향을 반대로 바꿔주고, 방향을 바꾼 다음 칸이 0일 경우와 1일 경우에 각각 해당하는 함수를 호출하여 이동하도록 하였다. 만약 다음 칸이 위 두 조건에 해당하지 않는다면 체스말은 그 자리를 그대로 유지하게 되는 것이다.

몇 시간 동안 문제를 고민하였지만 예제 5가 자꾸 -1을 출력하였고, 이는 아마도 2를 만난 코드 로직에서 문제가 있었던 것으로 생각된다. 결국은 다른 사람의 코드를 참고하였다.

Code

n, k = map(int, input().split())
cb = []
ch = []
chess = [[[] for _ in range(n)] for _ in range(n)]
dy = [0, 0, 0, -1, 1]
dx = [0, 1, -1, 0, 0]
def chk(nx, ny):
    if len(chess[nx][ny]) >= 4:
        return True
    return False
def case0(y, x, ny, nx, num):
    first = chess[y][x].index(num)
    last = len(chess[y][x])
    for k in range(first, last):
        ch[chess[y][x][k]][0] = ny
        ch[chess[y][x][k]][1] = nx
        chess[ny][nx].append(chess[y][x][k])
    for _ in range(first, last):
        chess[y][x].pop()
def case1(y, x, ny, nx, num):
    first = chess[y][x].index(num)
    last = len(chess[y][x])
    for k in range(last - 1, first - 1, - 1):
        ch[chess[y][x][k]][0] = ny
        ch[chess[y][x][k]][1] = nx
        chess[ny][nx].append(chess[y][x][k])
    for _ in range(first, last):
        chess[y][x].pop()
for i in range(n):
    cb.append(list(map(int, input().split())))
for i in range(k):
    y, x, d = map(int, input().split())
    chess[y-1][x-1].append(i)
    ch.append([y-1, x-1, d])
for i in range(1, 1001):
    for num in range(k):
        y, x, d = ch[num]
        ny = y+dy[d]
        nx = x+dx[d]
        if 0 <= ny < n and 0 <= nx < n and cb[ny][nx] == 0:
            case0(y, x, ny, nx, num)
            if chk(ny, nx):
                print(i)
                exit()
        elif 0 <= ny < n and 0 <= nx < n and cb[ny][nx] == 1:
            case1(y, x, ny, nx, num)
            if chk(ny, nx):
                print(i)
                exit()
        elif not (0 <= ny < n and 0 <= nx < n) or cb[ny][nx] == 2:
            if d == 1: d = 2
            elif d == 2: d = 1
            elif d == 3: d = 4
            elif d == 4: d = 3
            ch[num][2] = d
            ny = y+dy[d]
            nx = x+dx[d]
            if 0 <= ny < n and 0 <= nx < n and cb[ny][nx] == 0:
                case0(y, x, ny, nx, num)
                if chk(ny, nx):
                    print(i)
                    exit()
            elif 0 <= ny < n and 0 <= nx < n and cb[ny][nx] == 1:
                case1(y, x, ny, nx, num)
                if chk(ny, nx):
                    print(i)
                    exit()
else: print(-1)