시뮬레이션 - 루돌프의 반란

• 항상 조건문 쓸 때는 발생가능한 모든 경우의 수를 elif로 틀을 다 만들어 둔 후, 각각의 경우의 수 안으로 들어가기
• while True 쓸 때는 어떤 조건에서 break 걸어야 하는지 꼼꼼히 체크
• dx dy를 두개 이상 만드는 경우, 다른 dx dy랑 헷갈리지 않게 주의
• nx ny가 여러개인 경우 다른 nx ny랑 헷갈리지 않게 주의
• nx를 ny로 ny를 nx로 오타나지 않게 주의
• 우선순위는 항상 꼼꼼하게 체크
• 코드는 돌아가는데 답이 틀리는 경우, 대부분 알고리즘은 맞는데 변수나 정의를 실수한 것이므로 처음부터 코드 꼼꼼히 따라가면서 실수한 부분 찾아보기
• 자잘한 세부 조건들 꼼꼼히 체크하기
• 반복되는 부분은 함수화 가능하면 하기. 그래야 실수가 덜 나는듯
• nx ny 만들 땐 항상 범위 체크 잊지말기(맵 밖으로 나가면 안됨)
• 딕셔너리 쓸 때: dict.keys(), dict.values(), dict.items(), del dict[삭제할 키]
• 제곱: x**2
• 기절해서 n턴 쉬게 해야할 때는 2차원 리스트에 각 턴별로 기절한 산타 리스트 관리하기!
  if turn >= 1 and idx in sleep_santas[turn - 1]: continue
• sort(key=lambda x: [x[0], x[1]])

from collections import defaultdict

N, M, P, C, D = map(int, input().split())

Rr, Rc = map(int, input().split())

Rr, Rc = Rr - 1, Rc - 1 # 0부터 시작하도록 인덱스 맞추기

santas_score = defaultdict(int) # 점수
maps = [[0] * N for _ in range(N)]
santas = defaultdict(tuple)

game_over_santas = []
sleep_santas = [[] for _ in range(M)]

for i in range(P):
    line = tuple(map(int, input().split()))
    # 좌표 0부터 시작하도록 인덱스 맞추기
    santas_score[line[0]] = 0
    santas[line[0]] = (line[1] - 1, line[2] - 1)
    maps[line[1] - 1][line[2] - 1] = line[0]


# 산타의 방향을 반대로 바꾸는 함수
def turn_dir(d):
    if 0 <= d <= 1:
        return d + 2
    else:
        return d - 2


# 루돌프 초기 위치 맵에 -1로 표시
maps[Rr][Rc] = -1


for turn in range(M):
    # 1) 루돌프 움직임 -------------------------------------------------------------------------------

    # 모든 산타들과 루돌프 간의 거리 계산
    santa_list = list(santas.values())

    santa_list.sort(key=lambda x: [-x[0], -x[1]]) # 우선순위 대로 sort

    min_dist = float('inf')
    target_santa = (-1, -1)

    for Sr, Sc in santa_list:

        dist = (Rr - Sr)**2 + (Rc - Sc)**2

        if dist < min_dist:
            min_dist = dist
            target_santa = (Sr, Sc)
        

    # 가장 우선순위가 높은 산타와 가까워지는 칸으로 루돌프 1칸 이동

    dx = [-1, -1, -1, 0, 1, 1, 1, 0]
    dy = [-1, 0, 1, 1, 1, 0, -1, -1]
    # 루돌프 주변 8칸 모두 거리 체크

    r_to_s_dist = float('inf')
    R_nx, R_ny = -1, -1
    R_dir = -1

    for i in range(8):

        nx, ny = Rr + dx[i], Rc + dy[i]

        if 0 <= nx < N and 0 <= ny < N:
            dist = (nx - target_santa[0])**2 + (ny - target_santa[1])**2
            if dist < r_to_s_dist:
                r_to_s_dist = dist
                R_nx, R_ny = nx, ny
                R_dir = i

    # (R_nx, R_ny)로 루돌프 1칸 이동

    # 만약 해당 칸에 산타 있을 시 충돌
    if maps[R_nx][R_ny] > 0:
        # 충돌
        santa_num = maps[R_nx][R_ny]
        santas_score[santa_num] += C
        
        # 루돌프 이동
        maps[Rr][Rc] = 0
        maps[R_nx][R_ny] = -1
        Rr, Rc = R_nx, R_ny

        # 산타는 루돌프가 이동해온 방향(R_dir)으로 C칸 밀려남
        S_nx, S_ny = R_nx + (dx[R_dir] * C), R_ny + (dy[R_dir] * C)

        # 이번 턴에 기절한 산타 추가
        sleep_santas[turn].append(santa_num)

        # 맵 밖으로 밀려나갔다면 탈락
        if S_nx < 0 or S_nx >= N or S_ny < 0 or S_ny >= N:
            game_over_santas.append(santa_num)
            del santas[santa_num]

        # 맵 안인데 산타가 있는 자리라면
        elif 0 <= S_nx < N and 0 <= S_ny < N and maps[S_nx][S_ny] > 0:

            # 상호작용
            A_nx, A_ny = S_nx, S_ny
            move_santa_num = santa_num

            while True:
                another_santa_num = maps[A_nx][A_ny]
                maps[A_nx][A_ny] = move_santa_num
                santas[move_santa_num] = (A_nx, A_ny)

                # 밀려난 산타는 1칸 해당 방향으로 밀려남
                A_nx, A_ny = A_nx + dx[R_dir], A_ny + dy[R_dir]


                # 맵 밖으로 밀려나갔다면 탈락
                if A_nx < 0 or A_nx >= N or A_ny < 0 or A_ny >= N:
                    game_over_santas.append(another_santa_num)
                    del santas[another_santa_num]
                    
                    # 루프 종료!!!
                    break
                # 맵 안인데 산타가 있는 자리라면
                elif 0 <= A_nx < N and 0 <= A_ny < N and maps[A_nx][A_ny] > 0:
                    # 상호작용
                    move_santa_num = another_santa_num
                    continue
                # 맵 안인데 산타 없는 빈공간이라면
                elif 0 <= A_nx < N and 0 <= A_ny < N and maps[A_nx][A_ny] == 0:
                    maps[A_nx][A_ny] = another_santa_num
                    santas[another_santa_num] = (A_nx, A_ny)
                    break
        # 맵 안인데 산타 없는 빈공간이라면
        elif 0 <= S_nx < N and 0 <= S_ny < N and maps[S_nx][S_ny] == 0:
            maps[S_nx][S_ny] = santa_num
            santas[santa_num] = (S_nx, S_ny)

    else:
        # 루돌프 이동
        maps[Rr][Rc] = 0
        maps[R_nx][R_ny] = -1
        Rr, Rc = R_nx, R_ny



    # 2) 산타의 움직임 ------------------------------------------------------------------------------------------------------

    santa_list = list(santas.values())

    for idx in range(1, P + 1):

        if idx in sleep_santas[turn] or idx in game_over_santas:
            continue
        if turn >= 1 and idx in sleep_santas[turn - 1]:
            continue
        
        Sr, Sc = santas[idx]

        # 루돌프에게 가까워지는 방향 중 산타 없는 칸으로 1칸 이동

        dx_2 = [-1, 0, 1, 0] # 상 우 하 좌 우선순위
        dy_2 = [0, 1, 0, -1]

        min_dist = (Sr - Rr)**2 + (Sc - Rc)**2 # min_dist는 산타의 이동 전 좌표에서 루돌프까지의 거리로 초기화하기
        next_x, next_y = -1, -1
        santa_dir = -1

        for i in range(4):
            nx, ny = Sr + dx_2[i], Sc + dy_2[i] 

            # 맵 내부면서 산타 없는 칸이면
            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] <= 0:
                dist = (nx - Rr)**2 + (ny - Rc)**2
                
                # 기존 거리보다 작아지면서 최소값이라면 갱신
                if dist < min_dist:
                    min_dist = dist
                    next_x, next_y = nx, ny
                    santa_dir = i

        # 이동 불가라면 이동 X
        if next_x == -1 and next_y == -1:
            continue

        # 산타가 (next_x, next_y)로 이동
        maps[Sr][Sc] = 0
        
        # 만약 해당 칸에 루돌프가 있다면
        if maps[next_x][next_y] == -1:

            # 충돌
            santa_num = idx
            # 점수 얻기
            santas_score[santa_num] += D

            # 산타는 이동 방향의 반대 방향으로 D칸 밀려나기
            move_dir = turn_dir(santa_dir)

            S_nx, S_ny = next_x + (dx_2[move_dir] * D), next_y + (dy_2[move_dir] * D)


            # 이번 턴에 기절한 산타 추가
            sleep_santas[turn].append(santa_num)

            # 맵 밖으로 밀려나갔다면 탈락
            if S_nx < 0 or S_nx >= N or S_ny < 0 or S_ny >= N:
                game_over_santas.append(santa_num)
                del santas[santa_num]

            # 맵 안인데 산타가 있는 자리라면
            elif 0 <= S_nx < N and 0 <= S_ny < N and maps[S_nx][S_ny] > 0:

                # 상호작용
                A_nx, A_ny = S_nx, S_ny
                move_santa_num = santa_num

                while True:
                    another_santa_num = maps[A_nx][A_ny]
                    maps[A_nx][A_ny] = move_santa_num
                    santas[move_santa_num] = (A_nx, A_ny)

                    A_nx, A_ny = A_nx + dx_2[move_dir], A_ny + dy_2[move_dir] # 여기서 R_dir이랑 dx dy랑 혼동해서 씀!!!!

                    # 맵 밖으로 밀려나갔다면 탈락
                    if A_nx < 0 or A_nx >= N or A_ny < 0 or A_ny >= N:
                        game_over_santas.append(another_santa_num)
                        del santas[another_santa_num]

                        # 루프 종료!!!
                        break

                    # 맵 안인데 산타가 있는 자리라면
                    elif 0 <= A_nx < N and 0 <= A_ny < N and maps[A_nx][A_ny] > 0:
                        # 상호작용
                        move_santa_num = another_santa_num
                        continue

                    # 맵 안인데 산타 없는 빈공간이라면
                    elif 0 <= A_nx < N and 0 <= A_ny < N and maps[A_nx][A_ny] == 0:
                        maps[A_nx][A_ny] = another_santa_num
                        santas[another_santa_num] = (A_nx, A_ny)

                        break
            # 맵 안인데 산타 없는 빈공간이라면
            elif 0 <= S_nx < N and 0 <= S_ny < N and maps[S_nx][S_ny] == 0:
                maps[S_nx][S_ny] = santa_num
                santas[santa_num] = (S_nx, S_ny)

        # 해당 칸에 루돌프 없다면 그냥 이동
        else:
            maps[next_x][next_y] = idx
            santas[idx] = (next_x, next_y)


    # 만약 P명의 산타 모두 탈락 시 즉시 종료
    if len(game_over_santas) == P:
        break

    # 매 턴 끝나면 생존중인 산타 모두 +1점
    alive_santa = santas.keys()

    for s in alive_santa:
        santas_score[s] += 1



# 게임 종료 시 점수 출력

for i in range(1, P + 1):
    print(santas_score[i], end=" ")