[코드트리] - 루돌프의 반란 (파이썬, Python)

출처 : 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점씩을 추가로 부여합니다.

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

 

 

파이썬 풀이

from collections import deque

n, m, p, c, d = map(int, input().split())
RR, RC = map(int, input().split())
rx, ry = RR-1, RC-1
graph = [[0]*n for _ in range(n)]
graph[rx][ry] = -1

for _ in range(p):
    number, sx, sy = map(int, input().split())
    sx, sy = sx-1, sy-1
    graph[sx][sy] = number

alive = [1]*(p+1)
alive[0] = 0
stun = [0]*(p+1)
score = [0]*(p+1)

# 루돌프와 가장 가까운 산타 찾기
def find_nearest_santa(x, y):
    Q = deque()
    Q.append((x, y))
    dx = [1, -1, 0, 0, 1, 1, -1, -1]
    dy = [0, 0, 1, -1, 1, -1, 1, -1]
    visit = [[0]*n for _ in range(n)]
    visit[x][y] = 1
    temp = []
    SX, SY = x, y
    while Q:
        x, y = Q.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
                visit[nx][ny] = 1
                if graph[nx][ny] == 0:
                    Q.append((nx, ny))
                elif graph[nx][ny] > 0:
                    temp.append((nx, ny, abs(nx-SX)**2 + abs(ny-SY)**2))
    return sorted(temp, key=lambda x:(-x[2], x[0], x[1]))

# 루돌프 움직이기
def rudolf_move(x, y, ex, ey):
    Q = deque()
    Q.append((x, y))
    dx = [1, -1, 0, 0, 1, 1, -1, -1]
    dy = [0, 0, 1, -1, 1, -1, 1, -1]
    temp = []
    while Q:
        x, y = Q.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                temp.append((nx, ny, abs(ex-nx)**2 + abs(ey-ny)**2, dx[i], dy[i]))

    return sorted(temp, key=lambda x:(-x[2], x[0], x[1]))

# 루돌프가 움직여서 충돌
def rudolf_hit(x, y, number, dx, dy):
    nx = x + dx*c
    ny = y + dy*c
    if 0 <= nx < n and 0 <= ny < n:
        if graph[nx][ny] == 0:
            graph[nx][ny] = number

        elif graph[nx][ny] > 0:
            santa_hit_santa(nx, ny, graph[nx][ny], dx, dy)
            graph[nx][ny] = number

# 산타 움직이기
def santa_move(x, y, rx, ry):
    Q = deque()
    Q.append((x, y))
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    dist = abs(rx - x)**2 + abs(ry-y)**2
    temp = []
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            distance = abs(rx-nx)**2 + abs(ry-ny)**2
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] <= 0 and distance < dist:
                dist = distance
                temp.append((nx, ny, distance, dx[i], dy[i]))

    return sorted(temp, key=lambda x:(-x[2]))

# 산타가 움직여서 루돌프와 충돌
def santa_hit(x, y, number, dx, dy):
    nx = x + dx*d
    ny = y + dy*d
    if 0 <= nx < n and 0 <= ny < n:
        if graph[nx][ny] == 0:
            graph[nx][ny] = number

        elif graph[nx][ny] > 0:
            santa_hit_santa(nx, ny, graph[nx][ny], dx, dy)
            graph[nx][ny] = number

# 산타가 날아갔는데 산타와 충돌
def santa_hit_santa(x, y, number, dx, dy):
    Q = deque()
    Q.append((x, y, number))
    while Q:
        x, y, value = Q.popleft()
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < n:
            if graph[nx][ny] == 0:
                graph[nx][ny] = value
            elif graph[nx][ny] > 0:
                Q.append((nx, ny, graph[nx][ny]))
                graph[nx][ny] = value

# 스턴 1턴 제거
def stun_remove():
    for i in range(1, p+1):
        if stun[i] > 0:
            stun[i] -= 1

# 살아남은 산타 스코어 1 추가
def score_up():
    for i in range(1, p+1):
        if alive[i] == 1:
            score[i] += 1


for T in range(m):
    # 맵에 산타가 없으면 게임 끝
    if sum(alive) == 0:
        break

    # 가장 가까운 산타 찾기
    nearest = find_nearest_santa(rx, ry)
    ex, ey, r_dist = nearest.pop()
    graph[rx][ry] = 0

    # 루돌프 움직이기
    move_rudolf = rudolf_move(rx, ry, ex, ey)
    rx, ry, R_DIST, DX, DY = move_rudolf.pop()
    # 만약 루돌프가 산타와 부딪히면
    if R_DIST == 0:
        rudolf_hit(rx, ry, graph[rx][ry], DX, DY)
        stun[graph[rx][ry]] = 2
        score[graph[rx][ry]] += c
    graph[rx][ry] = -1

    # 살아남은 산타에 한해서 움직이기
    for z in range(1, p+1):
        santax, santay = -1, -1
        for i in range(n):
            for j in range(n):
                if graph[i][j] == z:
                    santax, santay = i, j

        if santax == -1 and santay == -1:
            continue

        number = z

        # 산타가 스턴 상태면 패스
        if stun[number] > 0:
            continue

        # 산타 이동
        move_santa = santa_move(santax, santay, rx, ry)

        # 만약 산타가 현재 이동할 수 없으면 패스
        if len(move_santa) == 0:
            continue

        graph[santax][santay] = 0
        sx, sy, s_dist, sdx, sdy = move_santa.pop()

        # 만약 산타가 루돌프와 부딪혔으면
        if s_dist == 0:
            santa_hit(sx, sy, number, -sdx, -sdy)
            stun[number] = 2
            score[number] += d

        # 안부딪혔으면
        else:
            graph[sx][sy] = number

    # 맵에 살아남은 산타 갱신
    alive = [0]*(p+1)
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0:
                alive[graph[i][j]] = 1

    # 스턴 1제거, 살아남은 스코어 1 추가
    stun_remove()
    score_up()

# 결과값 출력
for i in range(1, p+1):
    print(score[i], end=" ")