[Python/Codetree] 이상한 윷놀이

https://www.codetree.ai/training-field/frequent-problems/problems/odd-woodstick-game/submissions?page=2&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제

n * n 격자판에서 진행되는 새로운 규칙을 가진 윷놀이를 만들고자 합니다. 격자판은 흰색, 빨간색, 파란색 중 하나의 색을 가지고 있습니다. 말은 총 k개가 주어지며, 모두 격자판의 한 지점에 놓여있습니다. 1번부터 k번까지 번호가 지정되어 있으며 이동 방향 또한 미리 정해져있습니다. 상하좌우의 4가지 방향으로 움직일 수 있습니다.

턴 한 번동안 1번 말부터 k번 말까지 규칙대로 순서대로 움직입니다. 말을 옮기는 규칙은 다음과 같습니다.

• 말이 이동하려는 칸이 흰색인 경우에는 해당 칸으로 이동합니다. 이동하려는 칸에 말이 이미 있는 경우에는 해당 말 위에 이동하려던 말을 올려둡니다. 이미 말이 올려져 있는 상태에도 말을 올릴 수 있습니다.

• 이동하려는 칸이 빨간색인 경우에는 해당 칸으로 이동하기 전 순서를 뒤집습니다. 이후 해당 칸에 말이 있는 경우에는 흰색 칸과 같이 그 위에 쌓아둡니다.

• 이동하려는 칸이 파란색일 경우에는 이동하지 않고 방향을 반대로 전환한 뒤 이동합니다. 만일 반대 방향으로 전환한 뒤 이동하려는 칸도 파란색이라면 방향만 반대로 전환한 뒤 이동하지 않고 가만히 있습니다. 이동하려는 말에 다른 말들이 쌓여있을 경우에 이동하려는 말만 방향을 반대로 바꿔야 함에 유의합니다.

• 격자판의 범위를 벗어나는 이동일 경우 파란색으로 이동하려는 것과 똑같이 생각하여 처리해줍니다.

• 쌓여있는 말을 이동하는 경우에는 본인 위에 있는 말과 함께 이동해줍니다. 예를 들어 A, B, C, D 네 개의 말이 있는 상태에서 알파벳 순서대로 말을 이동시키며 한 턴을 진행한다고 하면 다음과 같이 변화되는 것을 알 수 있습니다.

게임이 진행되는 동안 아직 한 턴이 다 끝나지 않은 경우더라도 말이 4개 이상 겹쳐지는 경우가 생긴다면 그 즉시 게임을 종료합니다. 위의 그림은 이해를 돕기 위한 예시이며 초기 상태에 4개 이상 겹쳐진 입력은 주어지지 않습니다.

격자판의 상태와 말의 위치, 이동 방향이 주어질 때 게임이 종료되는 순간의 턴의 번호를 구하는 프로그램을 설계하세요.

풀이

Code

from collections import deque

# 1. 말 갯수 체크 함수 정의
def check(x, y) :
    # 1-1. 말의 갯수가 4개 이상인 경우 False 반환
    return False if len(graph[x][y]) >= 4 else True
# 2. 흰색 이동칸 함수 정의
def move_white(i, x, y, nx, ny) :
    # 2-1. 말의 위치 찾기
    idx = graph[x][y].index(i)
    # 2-2. 말 이동
    for j in range(idx+1) :
        num = graph[x][y][0]
        piece[num][0], piece[num][1] = nx, ny
        graph[nx][ny].insert(j, graph[x][y].popleft())
# 3. 빨간색 이동칸 함수 정의
def move_red(i, x, y, nx, ny) :
    # 3-1. 말의 위치 찾기
    idx = graph[x][y].index(i)
    # 3-2. 말 이동
    for j in range(idx+1) :
        num = graph[x][y][0]
        piece[num][0], piece[num][1] = nx, ny
        graph[nx][ny].appendleft(graph[x][y].popleft())
# 4. 파란색 이동칸 함수 정의
def move_blue(i, x, y) :
    # 4-1. 방향 변환
    dir = piece[i][2]
    if dir == 1 : dir = 2
    elif dir == 2 : dir = 1
    elif dir == 3 : dir = 4
    else : dir = 3
    piece[i][2] = dir
    # 4-2. 바뀐 방향이 파란색이 아닐 경우
    nx, ny = x + dirs[dir][0], y + dirs[dir][1]
    if 0 <= nx < n and 0 <= ny < n and color_graph[nx][ny] != 2 :
        # 다음 칸이 흰색인 경우
        if color_graph[nx][ny] == 0 : move_white(i, x, y, nx, ny)
        # 다음 칸이 빨간색인 경우
        else : move_red(i, x, y, nx, ny)
        return nx, ny
    return x, y
# 5. 말 이동 함수 정의
def move() :
    # 5-1.
    for i, information in enumerate(piece) :
        x, y, dir = information
        # 5-1-1. 말의 다음 위치 정의
        nx, ny = x + dirs[dir][0], y + dirs[dir][1]
        # 5-1-2. 다음 위치가 맵에서 벗어나거나 파란색 칸인 경우
        if nx < 0 or nx >= n or ny < 0 or ny >= n or color_graph[nx][ny] == 2 : nx, ny = move_blue(i, x, y)
        # 5-1-3. 다음 위치가 흰색 칸인 경우
        elif color_graph[nx][ny] == 0 : move_white(i, x, y, nx, ny)
        # 5-1-4. 다음 위치가 빨간색 칸인 경우
        elif color_graph[nx][ny] == 1 : move_red(i, x, y, nx, ny)
        # 5-1-5. 말 갯수 체크
        if not check(nx, ny) : return False
    # 5-2. True 반환
    return True

n, k = map(int, input().split())
color_graph = [list(map(int, input().split())) for _ in range(n)]
dirs = [(), (0, 1), (0, -1), (-1, 0), (1, 0)]

# 6. 불가능한 경우를 위한 변수 생성
impossible = False
# 7. 그래프 생성
graph = [[deque() for _ in range(n)] for _ in range(n)]
# 8. 말 리스트 생성
piece = []
# 9.
for i in range(k) :
    x, y, dir = map(int, input().split())
    x -= 1
    y -= 1
    # 불가능한 위치인 경우
    if x < 0 or x >= n or y < 0 or y >= n :
        impossible = True
        break
    # 말 위치 정보 입력
    piece.append([x, y, dir])
    graph[x][y].append(i)
# 10. 불가능한 경우 -1 출력
if impossible : print(-1)
# 11. 이외의 경우
else :
    # 11-1. 카운트 변수 생성
    cnt = 0
    # 11-2.
    while cnt <= 1000 :
        # 11-2-1. 카운트
        cnt += 1
        # 11-2-2. 말 이동 결과가 False 경우 탈출
        if not move() : break
    # 11-3. 결과 출력
    print(cnt if cnt <= 1000 else -1)