[Python/Codetree] 싸움땅

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

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

문제

인기 게임인 싸움땅은 다음과 같은 방식으로 진행됩니다. 게임은 n * n 크기의 격자에서 진행되며, 각각의 격자에는 무기들이 있을 수 있습니다. 초기에는 무기들이 없는 빈 격자에 플레이어들이 위치하며 각 플레이어는 초기 능력치를 가집니다. 각 플레이어의 초기 능력치는 모두 다릅니다. 게임은 다음과 같은 방식으로 진행됩니다.

아래 그림에서 빨간색 배경의 숫자는 총의 경우 공격력을, 플레이어의 경우 초기 능력치를 의미하며, 노란색 배경의 숫자는 플레이어의 번호를 의미합니다.

하나의 라운드는 다음의 과정에 걸쳐 진행됩니다.

1-1. 첫 번째 플레이어부터 순차적으로 본인이 향하고 있는 방향대로 한 칸만큼 이동합니다. 만약 해당 방향으로 나갈 때 격자를 벗어나는 경우에는 정반대 방향으로 방향을 바꾸어서 1만큼 이동합니다.

2-1. 만약 이동한 방향에 플레이어가 없다면 해당 칸에 총이 있는지 확인합니다. 총이 있는 경우, 해당 플레이어는 총을 획득합니다. 플레이어가 이미 총을 가지고 있는 경우에는 놓여있는 총들과 플레이어가 가지고 있는 총 가운데 공격력이 더 쎈 총을 획득하고, 나머지 총들은 해당 격자에 둡니다.

2-2-1. 만약 이동한 방향에 플레이어가 있는 경우에는 두 플레이어가 싸우게 됩니다. 해당 플레이어의 초기 능력치와 가지고 있는 총의 공격력의 합을 비교하여 더 큰 플레이어가 이기게 됩니다. 만일 이 수치가 같은 경우에는 플레이어의 초기 능력치가 높은 플레이어가 승리하게 됩니다. 이긴 플레이어는 각 플레이어의 초기 능력치와 가지고 있는 총의 공격력의 합의 차이만큼을 포인트로 획득하게 됩니다.

2-2-2. 진 플레이어는 본인이 가지고 있는 총을 해당 격자에 내려놓고, 해당 플레이어가 원래 가지고 있던 방향대로 한 칸 이동합니다. 만약 이동하려는 칸에 다른 플레이어가 있거나 격자 범위 밖인 경우에는 오른쪽으로 90도씩 회전하여 빈 칸이 보이는 순간 이동합니다. 만약 해당 칸에 총이 있다면, 해당 플레이어는 가장 공격력이 높은 총을 획득하고 나머지 총들은 해당 격자에 내려 놓습니다.

2-2-3. 이긴 플레이어는 승리한 칸에 떨어져 있는 총들과 원래 들고 있던 총 중 가장 공격력이 높은 총을 획득하고, 나머지 총들은 해당 격자에 내려 놓습니다.

위 과정을 1번부터 n번 플레이어까지 순차적으로 한 번씩 진행하면 1 라운드가 끝나게 되고, 그 결과는 다음과 같습니다.

1번 라운드에 걸쳐 전체 플레이어가 획득한 포인트는 1번 사람부터 n번 사람까지 순서대로 [1, 0, 0, 0]입니다.

위의 과정을 한번더 반복하여 나온 2번 라운드 결과는 다음과 같으며, 2번 라운드 이후 획득한 포인트 역시 1번 라운드와 동일하게 [1, 0, 0, 0]이 됩니다.

k 라운드 동안 게임을 진행하면서 각 플레이어들이 획득한 포인트를 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 n, m, k가 공백을 사이에 두고 주어집니다. n은 격자의 크기, m은 플레이어의 수, k는 라운드의 수를 의미합니다.

이후 n개의 줄에 걸쳐 격자에 있는 총의 정보가 주어집니다. 각 줄에는 각각의 행에 해당하는 n개의 수가 공백을 사이에 두고 주어집니다. 숫자 0은 빈 칸, 0보다 큰 값은 총의 공격력을 의미합니다.

이후 m개의 줄에 걸쳐 플레이어들의 정보 x, y, d, s가 공백을 사이에 두고 주어집니다. (x, y)는 플레이어의 위치, d는 방향, s는 플레이어의 초기 능력치를 의미하고 각 플레이어의 초기 능력치는 모두 다릅니다. 방향 d는 0부터 3까지 순서대로 ↑, →, ↓, ←을 의미합니다.

각 플레이어의 위치는 겹쳐져 주어지지 않으며, 플레이어의 초기 위치에는 총이 존재하지 않습니다.

• 2 ≤ n ≤ 20
• 1 ≤ m ≤ min(n2,30)
• 1 ≤ k ≤ 500
• 1 ≤ 총의 공격력 ≤ 100,000
• 1 ≤ s ≤ 100
• 1 ≤ x, y ≤ n

출력 형식

k 라운드 동안 게임을 진행하면서 각 플레이어들이 획득한 포인트를 공백을 사이에 두고 출력하세요.

문제요약

풀이

Code

from heapq import heappop, heappushpop, heappush

# 1. 플레이어 이동 함수 정의
def move(i) :
    x, y = information[i][1], information[i][2]
    # 1-1. 다음 위치로 이동
    dir = information[i][0]
    nx, ny = x + dirs[dir][0], y + dirs[dir][1]
    # 격자를 벗어나는 경우 플레이어 방향 재설정 및 이동
    if nx < 1 or nx > n or ny < 1 or ny > n :
        dir = (dir + 2) % 4
        information[i][0] = dir
        nx, ny = x + dirs[dir][0], y + dirs[dir][1]
    information[i][1], information[i][2] = nx, ny
    # 위치 리스트 업데이트
    players_map[x][y] = 0
    # 1-2. 해당 위치에 다른 플레이어가 있는 경우
    if players_map[nx][ny] :
        # 플레이어 전투 함수 실행
        fight(i, players_map[nx][ny], nx, ny)
    # 1-3. 플레이어가 없는 경우
    else :
        # 이동한 위치 리스트 업데이트
        players_map[nx][ny] = i
        # 해당 위치에 총이 있을 경우
        if guns_map[nx][ny] :
            # 플레이어가 총이 없는 경우
            if not information[i][4] : information[i][4] = -heappop(guns_map[nx][ny])
            # 플레이어가 총이 있는 경우
            else :
                information[i][4] = -heappushpop(guns_map[nx][ny], -information[i][4])
# 2. 플레이어 전투 함수 정의
def fight(p1, p2, x, y) :
    # 2-1. 승자, 패자 정하기
    if information[p1][3] + information[p1][4] > information[p2][3] + information[p2][4] : winner, loser = p1, p2
    elif information[p1][3] + information[p1][4] < information[p2][3] + information[p2][4]: winner, loser = p2, p1
    else :
        if information[p1][3] > information[p2][3] : winner, loser = p1, p2
        elif information[p1][3] < information[p2][3] : winner, loser = p2, p1
    # 2-2. 승자 포인트 획득
    information[winner][-1] += (information[winner][3] + information[winner][4]) - (information[loser][3] + information[loser][4])
    # 2-3. 패자의 경우
    # 2-3-1. 총 내려놓기
    information[loser][4], gun = 0, information[loser][4]
    loser_x, loser_y = information[loser][1], information[loser][2]
    if gun > 0 : heappush(guns_map[loser_x][loser_y], -gun)
    # 2-3-2.
    now_dir = information[loser][0]
    for idx in range(now_dir, now_dir + 4) :
        # 다음 위치 인덱스 생성
        idx %= 4
        nx, ny = x + dirs[idx][0], y + dirs[idx][1]
        # 다음 위치에 플레이어가 있거나 격자 범위 밖인 경우 continue
        if nx < 1 or nx > n or ny < 1 or ny > n or players_map[nx][ny] : continue
        # 플레이어 정보에 방향 업데이트
        information[loser][0] = idx
        # 이동 & 위치 리스트 업데이트
        information[loser][1], information[loser][2] = nx, ny
        players_map[loser_x][loser_y], players_map[nx][ny] = 0, loser
        # 해당 위치에 총이 있을 경우 공격력이 가장 높은 총 획득
        if guns_map[nx][ny] : information[loser][4] = -heappop(guns_map[nx][ny])
        break
    # 2-4. 승자의 경우
    # 2-4-1. 승리한 칸에 떨어져 있는 총들과 자신이 가진 총 중 공격력이 가장 높은 총 획득
    players_map[x][y] = winner
    winner_x, winner_y = x, y
    information[winner][4] = -heappushpop(guns_map[winner_x][winner_y], -information[winner][4])

n, m, k = map(int, input().split())
guns_map = [[0 for _ in range(n+1)]] + [([0] + list(map(int, input().split()))) for _ in range(n)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# 3. 인덱스 별 최대힙으로 만들어 삽입
for i in range(1, n+1) :
    for j in  range(1, n+1) :
        number, guns_map[i][j] = guns_map[i][j], []
        if number > 0 : heappush(guns_map[i][j], -number)

# 4. 플레이어 정보 리스트 생성 -> [방향, 위치 x, 위치 y, 초기 능력치, 총 공격력, 스코어]
information = [[]]
for _ in range(m) :
    x, y, d, s = map(int, input().split())
    information.append([d, x, y, s, 0, 0])
# 5. 플레이어 위치 리스트 생성
players_map = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, m+1) :
    x, y = information[i][1], information[i][2]
    players_map[x][y] = i
# 6.
for _ in range(k) :
    # 6-1.
    for i in range(1, m+1) :
        # 이동 함수 실행
        move(i)
# 7. 결과 출력
print(*[info[-1] for info in information[1:]])