[Python/Codetree] 루돌프의 반란

https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion/description?page=1&pageSize=20

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

문제

1번부터 P번까지 P 명의 산타들이 크리스마스 이브를 준비하던 중, 산타의 주요 수송수단인 루돌프가 반란을 일으켰습니다. 루돌프는 산타들을 박치기하여 산타의 선물 배달을 방해하려고 합니다. 산타들은 루돌프를 잡아서 크리스마스를 구해야 합니다!

(1) 게임판의 구성

• 게임판은 N×N 크기의 격자로 이루어져 있습니다. 각 위치는 (r,c)의 형태로 표현되며, 아래로 갈수록 r이 증가, 오른쪽으로 갈수록 c가 증가합니다. 좌상단은 (1,1)입니다.
• 게임은 총 M 개의 턴에 걸쳐 진행되며 매 턴마다 루돌프와 산타들이 한 번씩 움직입니다. 루돌프가 한 번 움직인 뒤, 1번 산타부터 P번 산타까지 순서대로 움직이게 됩니다. 이때 기절해있거나 격자 밖으로 빠져나가 게임에서 탈락한 산타들은 움직일 수 없습니다.
• 게임판에서 두 칸 (r1​,c1​), (r2​,c2​) 사이의 거리는 (r1​−r2​)2+(c1​−c2​)2으로 계산됩니다.

(2) 루돌프의 움직임

• 루돌프는 가장 가까운 산타를 향해 1칸 돌진합니다. 단, 게임에서 탈락하지 않은 산타 중 가장 가까운 산타를 선택해야 합니다.
• 만약 가장 가까운 산타가 2명 이상이라면, r 좌표가 큰 산타를 향해 돌진합니다. r이 동일한 경우, c 좌표가 큰 산타를 향해 돌진합니다.
• 루돌프는 상하좌우, 대각선을 포함한 인접한 8방향 중 하나로 돌진할 수 있습니다. (편의상 인접한 대각선 방향으로 전진하는 것도 1칸 전진하는 것이라 생각합니다.) 가장 우선순위가 높은 산타를 향해 8방향 중 가장 가까워지는 방향으로 한 칸 돌진합니다.

(3) 산타의 움직임

• 산타는 1번부터 P번까지 순서대로 움직입니다.
• 기절했거나 이미 게임에서 탈락한 산타는 움직일 수 없습니다.
• 산타는 루돌프에게 거리가 가장 가까워지는 방향으로 1칸 이동합니다.
• 산타는 다른 산타가 있는 칸이나 게임판 밖으로는 움직일 수 없습니다.
• 움직일 수 있는 칸이 없다면 산타는 움직이지 않습니다.
• 움직일 수 있는 칸이 있더라도 만약 루돌프로부터 가까워질 수 있는 방법이 없다면 산타는 움직이지 않습니다.
• 산타는 상하좌우로 인접한 4방향 중 한 곳으로 움직일 수 있습니다. 이때 가장 가까워질 수 있는 방향이 여러 개라면, 상우하좌 우선순위에 맞춰 움직입니다.

(4) 충돌

• 산타와 루돌프가 같은 칸에 있게 되면 충돌이 발생합니다.
• 루돌프가 움직여서 충돌이 일어난 경우, 해당 산타는 C만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 루돌프가 이동해온 방향으로 C 칸 만큼 밀려나게 됩니다.
• 산타가 움직여서 충돌이 일어난 경우, 해당 산타는 D만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 자신이 이동해온 반대 방향으로 D 칸 만큼 밀려나게 됩니다.
• 밀려나는 것은 포물선 모양을 그리며 밀려나는 것이기 때문에 이동하는 도중에 충돌이 일어나지는 않고 정확히 원하는 위치에 도달하게 됩니다.
• 만약 밀려난 위치가 게임판 밖이라면 산타는 게임에서 탈락됩니다.
• 만약 밀려난 칸에 다른 산타가 있는 경우 상호작용이 발생합니다.

(5) 상호작용

• 루돌프와의 충돌 후 산타는 포물선의 궤적으로 이동하여 착지하게 되는 칸에서만 상호작용이 발생할 수 있습니다.
• 산타는 충돌 후 착지하게 되는 칸에 다른 산타가 있다면 그 산타는 1칸 해당 방향으로 밀려나게 됩니다. 그 옆에 산타가 있다면 연쇄적으로 1칸씩 밀려나는 것을 반복하게 됩니다. 게임판 밖으로 밀려나오게 된 산타의 경우 게임에서 탈락됩니다.

(6) 기절

• 산타는 루돌프와의 충돌 후 기절을 하게 됩니다. 현재가 k번째 턴이었다면, (k+1)번째 턴까지 기절하게 되어 (k+2)번째 턴부터 다시 정상상태가 됩니다.
• 기절한 산타는 움직일 수 없게 됩니다.
• 루돌프는 기절한 산타를 돌진 대상으로 선택할 수 있습니다.

(7) 게임 종료

• M 번의 턴에 걸쳐 루돌프, 산타가 순서대로 움직인 이후 게임이 종료됩니다.
• 만약 P 명의 산타가 모두 게임에서 탈락하게 된다면 그 즉시 게임이 종료됩니다.
• 매 턴 이후 아직 탈락하지 않은 산타들에게는 1점씩을 추가로 부여합니다.

게임이 끝났을 때 각 산타가 얻은 최종 점수를 구하는 프로그램을 작성해보세요.

풀이

Code

import sys
input = sys.stdin.readline

# 1. 루돌프와 산타의 최소 거리 계산 함수 정의
def calculate_dist(who) :
    target_x, target_y = santa[who]["idx"]
    # 1-1. 거리, 방향 변수 생성
    update_dist, update_dir = float("INF"), 0
    # 1-2.
    for dir, (dir_x, dir_y) in enumerate(dirs_r) :
        nrr, nrc = rr + dir_x, rc + dir_y
        # 1-2-1. 거리 계산
        dist = (nrr - target_x)**2 + (nrc - target_y)**2
        # 1-2-1. 거리가 가까워질 경우 거리, 방향 변수 업데이트
        if dist < update_dist :
            update_dist, update_dir = dist, dir
    # 1-3. 거리, 방향 반환
    return update_dir
# 2. 루돌프 이동 함수 정의
def move_roodolph() :
    global rr, rc
    # 2-1. 최종 이동 방향, 거리, 최종 타겟 인덱스 변수 생성
    target = -1
    target_x, target_y = -1, -1
    update_dist = float("INF")
    # 2-2. 산타 타겟 설정
    for who in santa.keys() :
        x, y = santa[who]["idx"]
        # 2-2-1. 거리 계산
        dist = (rr - x)**2 + (rc - y)**2
        # 2-2-2. 거리 업데이트
        if dist <= update_dist :
            x, y = santa[who]["idx"]
            # 거리가 같을 경우 산타의 위치에 따라 업데이트
            if dist == update_dist :
                if target_x <= x :
                    if (target_x < x) or (target_x == x and target_y < y) :
                        target = who
                        target_x, target_y = x, y
            else :
                target = who
                target_x, target_y = x, y
                update_dist = dist
    # 2-3. 루돌프 이동 방향 설정
    dir = calculate_dist(target)
    # 2-4. 루돌프 이동
    nrr, nrc = rr + dirs_r[dir][0], rc + dirs_r[dir][1]
    # 2-5. 해당 위치에 산타가 있을 경우
    if graph[nrr][nrc] :
        # 2-5-1. 산타 기절 업데이트
        santa[graph[nrr][nrc]]["faint_stack"] = 2
        # 2-5-2. 충돌 시 산타 이동 함수 실행
        smash("r2s", graph[nrr][nrc], dir)
    graph[rr][rc] = 0
    graph[nrr][nrc] = -1
    rr, rc = nrr, nrc
# 3. 산타의 이동 방향 결정 함수 정의
def select_dir(who) :
    x, y = santa[who]["idx"]
    # 3-1. 거리, 방향 변수 생성
    update_dist, update_dir = (rr - x) ** 2 + (rc - y) ** 2, -1
    # 3-2.
    for dir, (dir_x, dir_y) in enumerate(dirs_s) :
        # 3-2-1. 다음 방향 설정
        nx, ny = x + dir_x, y + dir_y
        # 3-2-2. 예외 처리
        if nx < 0 or nx >= n or ny < 0 or ny >= n or graph[nx][ny] > 0: continue
        # 3-2-3. 거리 계산
        dist = (rr - nx)**2 + (rc - ny)**2
        # 3-2-4. 거리 업데이트
        if dist < update_dist :
            update_dist, update_dir = dist, dir
    # 3-3. 방향 반환
    return update_dir
# 4. 산타 이동 함수 정의
def move_santa() :
    # 4-1.
    for who in sorted(list(santa.keys())) :
        try :
            # 4-1-1. 산타 기절 시 continue
            if santa[who]["faint_stack"] :
                santa[who]["faint_stack"] -= 1
                continue
            # 4-1-2. 산타 이동 방향 선정
            dir = select_dir(who)
            x, y = santa[who]["idx"]
            if dir != -1 :
                nx, ny = x + dirs_s[dir][0], y + dirs_s[dir][1]
            else :
                nx, ny = x, y
            # 4-1-3. 이동 위치에 루돌프가 있는 경우
            if (nx, ny) == (rr, rc) :
                # 산타 기절 업데이트
                santa[who]["faint_stack"] = 1
                # 충돌 시 산타 이동 함수 실행
                smash("s2r", who, dir)
            # 4-1-4. 이외의 경우 산타 이동
            else :
                graph[x][y], graph[nx][ny] = 0, who
                santa[who]["idx"] = [nx, ny]
        except : pass
# 5. 충돌 시 산타 이동 함수 정의
def smash(way, who, dir) :
    x, y = santa[who]["idx"]
    # 5-1. 산타 점수 획득
    santa[who]['score'] += c if way == "r2s" else d
    # 5-2. 튕겨져 나갈 방향 설정
    if way == "r2s" :
        dir_x, dir_y = dirs_r[dir][0], dirs_r[dir][1]
    else :
        new_dir = (dir + 2) % len(dirs_s)
        dir_x, dir_y = dirs_s[new_dir][0], dirs_s[new_dir][1]
    # 5-3. 튕겨져 나갈 거리 설정
    how = c+1 if way == 'r2s' else d
    # 5-4. 튕겨진 위치 구하기
    santa[who]["idx"] = [x + dir_x * (how - 2), y + dir_y * (how - 2)]
    next = who
    # 5-5.
    while True :
        # 5-5-1. 다음 위치 정의
        mx, my = santa[next]["idx"][0], santa[next]["idx"][1]
        nx, ny = mx + dir_x, my + dir_y
        # 5-5-2. 다음 위치가 맵을 벗어날 경우
        if nx < 0 or nx >= n or ny < 0 or ny >= n :
            # 그래프 업데이트
            if who == next :
                graph[x][y] = 0
            else :
                graph[mx][my] = 0
            # 게임 탈락 처리
            leaving_out(who)
            # while문 탈출
            break
        # 5-5-3. 그래프 업데이트
        if who == next:
            graph[x][y] = 0
        else:
            graph[mx][my] = 0
        # 5-5-4. 산타 정보 업데이트
        santa[who]["idx"] = [nx, ny]
        # 5-5-5. 다른 산타가 있는 경우
        if graph[nx][ny] :
            # 다음 처리되어야 할 산타 지정
            next = graph[nx][ny]
            # 그래프 업데이트
            graph[nx][ny] = who
        # 5-5-6. 다음 위치에 아무도 없는 경우
        else :
            # 그래프 업데이트
            graph[nx][ny] = who
            # while문 탈출
            break
        who = next
# 6. 게임 탈락 처리 함수 정의
def leaving_out(who) :
    # 6-1. 해당 산타의 최종 점수 등록
    final_score[who] = santa[who]["score"]
    # 6-2. 산타 정보 제거
    del santa[who]
# 7, 추가 점수 부여 함수 정의
def give_extra_points() :
    # 7-1.
    for who in santa.keys() :
        # 추가 점수 부여
        santa[who]["score"] += 1

if __name__ == "__main__" :
    n, m, p, c, d = map(int, input().split())
    # 8. 그래프 생성
    graph = [[0 for _ in range(n)] for _ in range(n)]
    rr, rc = map(int, input().split())
    rr -= 1
    rc -= 1
    graph[rr][rc] = -1
    # 9. 산타 정보 생성
    santa = dict()
    for _ in range(1, p+1) :
        pn, sr, sc = map(int, input().split())
        santa[pn] = {"faint_stack" : 0, "idx" : [sr-1, sc-1], "score" : 0}
        graph[sr-1][sc-1] = pn
    # 10. 루돌프 이동 방향 변수 생성
    dirs_r = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
    # 11. 산타 이동 방향 변수 생성
    dirs_s = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    # 12. 최종 점수 리스트 생성
    final_score = [0 for _ in range(p+1)]
    # 13.
    for _ in range(m) :
        # 13-1. 루돌프 이동
        move_roodolph()
        # 13-2. 산타 이동
        move_santa()
        # 13-3. 게임 종료 여부 판단
        if not santa : break
        # 13-4. 추가 점수 부여
        give_extra_points()
    # 14. 최종 점수 리스트 업데이트
    for who in santa.keys() :
        final_score[who] = santa[who]["score"]
    # 15. 결과 출력
    print(*final_score[1:])