이번 문제는 삼성 기출 문제로, 문제를 꼼꼼히 읽고 구현하였다. 각각의 말들을 (좌표, 번호, 방향)의 형태로 p라는 리스트에 담아놓았고, location이라는 3차원 리스트에 해당 말의 좌표에 해당하는 칸에 말의 번호를 담았다. 이는 말이 여러 개 있을 때, 쌓여있는 순서를 구현하기 위한 것이다. p에 따로 말들의 정보를 넣은 이유는, 해당 좌표만을 탐색하여 시간을 줄이기 위함이었다.

move_p라는 함수에서 p를 순회하며 p에 저장된 자표로 location리스트에 접근하고, 현재 말의 번호가 해당 좌표의 location의 가장 앞에 있을 경우에만 이동을 하도록 하였고, 이동을 할 때는 다음 칸이 범위 내에 있는지, 다음 칸이 무슨 색인지를 판별하도록 하였다.

범위 내에 있고, 흰색이나 빨간색일 경우에는 우선 해당 좌표의 location을 순회하며 p의 좌표들을 다음 칸으로 갱신해주고, 흰색일 경우, 다음 좌표의 location에 현재 좌표의 location을 붙이고, 현재 좌표의 location을 빈 리스트로 갱신하였다. 빨간색일 경우, 다음 좌표의 location에 현재 좌표의 location을 뒤집어 붙였고, 현재 좌표의 location을 빈 리스트로 갱신하였다.

범위 내에 없거나, 파란색일 경우에는 우선 현재 말의 이동 방향을 반대방향으로 갱신해주었고, 다시 다음칸을 확인하여 흰색이나 빨간색일 경우는 위의 과정을 진행하도록, 파란색일 경우에는 현재 위치를 유지하도록 하였다.

이 과정이 모두 끝나면 다음 좌표의 location을 확인하여 4 이상일 경우에 현재의 순서 변수를 출력하고 프로그램을 종료하도록 하였다.

Code

n, k = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
location = [[[] for _ in range(n)] for _ in range(n)]
p = []
for i in range(1, k+1):
    py, px, pd = map(int, input().split())
    p.append((py-1, px-1, i, pd-1))
    location[py-1][px-1].append(i)
dy, dx = [0, 0, -1, 1], [1, -1, 0, 0]
turn = 1
def move_p():
    for i in range(k):
        y, x, num, d = p[i]
        if len(location[y][x]):
            if location[y][x][0] == num:
                ny, nx = y+dy[d], x+dx[d]
                if 0 <= ny < n and 0 <= nx < n and grid[ny][nx] != 2:
                    for j in range(k):
                        if p[j][2] in set(location[y][x]):
                            p[j] = (ny, nx, p[j][2], p[j][3])
                    if grid[ny][nx] == 0:
                            location[ny][nx], location[y][x] = location[ny][nx]+location[y][x], []
                    elif grid[ny][nx] == 1:
                            location[ny][nx], location[y][x] = location[ny][nx]+location[y][x][::-1], []
                else:
                    if d%2 == 0:
                        d = (d+1)%4
                    else:
                        d = (d-1)%4
                    p[i] = (y, x, num, d)
                    ny, nx = y+dy[d], x+dx[d]
                    if 0 <= ny < n and 0 <= nx < n and grid[ny][nx] != 2:
                        for j in range(k):
                            if p[j][2] in set(location[y][x]):
                                p[j] = (ny, nx, p[j][2], p[j][3])
                        if grid[ny][nx] == 0:
                            location[ny][nx], location[y][x] = location[ny][nx] + location[y][x], []
                        elif grid[ny][nx] == 1:
                            location[ny][nx], location[y][x] = location[ny][nx] + location[y][x][::-1], []
                    else:
                        ny, nx = y, x
                if len(location[ny][nx]) >= 4:
                    print(turn)
                    quit()
while turn <= 1000:
    move_p()
    turn += 1
print(-1)