2022하_싸움땅(2024/04/06 업데이트)

문제

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

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

해설(v2 기준)

1. 초기 설정
   
   1. 총, 플레이어 맵을 각각 요소가 빈 배열인 2차원 리스트로 선언한다.
   2. 플레이어 리스트를 선언한다.
   3. 플레이어는 class 로 선언하여 모든 특징을 갖게 한다.
   4. 탐색 방향은 상,우,하,좌이다. 이를 통해 아래 조건을 만족한다.
      1. 플레이어의 방향 d는 0부터 3까지 순서대로 ↑, →, ↓, ←을 의미합니다.
2. 전체 프로세스
   1. 플레이어별 순차 이동
      1. 만약 해당 방향으로 나갈 때 격자를 벗어나는 경우 방향 정반대로 바꾸기
      2. 1만큼 move
      3. 만약 이동한 칸에 플레이어가
         1. 없다면 
            1. 해당 칸에 총이 있는지 확인
               1. 플레이어가 이미 총 갖고 있으면 drop
            2. 총이 있으면 총 get
         2. 있다면
            1. 두 플레이어 fight
               
               1. loser는 lose
               2. winner는 win
3. 개별 함수 설명
   1. move
      1. 플레이어가 현재 칸에서 다음 칸으로 이동한다.
   2. drop
      1. 플레이어가 자신의 무기를 현재 위치한 총 맵에 내려놓는다.
   3. get
      1. 플레이어가 현재 위치한 총 맵에서 가장 공격력이 높은 무기를 획득한다.
   4. lose
      1. 총 drop
      2. 원래 방향대로 한 칸 move
         1. 만약 이동하려는 칸에 다른 플레이어 있거나 격자 범위 밖인 경우 오른쪽으로 90도씩 회전하여 이동 가능한 칸 찾아서 move
      3. 만약 해당 칸에 총이 있다면, get
   5. win
      1. drop
      2. get

소스코드

v2(2024.04.06)

import sys

input = sys.stdin.readline

class Player:
    def __init__(self, no, x, y, d, s, g=0, p=0):
        self.no = no
        self.x = x
        self.y = y
        self.d = d
        self.s = s
        self.g = g
        self.p = p

n, m, K = map(int, input().split())
a = [[[] for _ in range(n)] for _ in range(n)]  # 총 맵
b = [[[] for _ in range(n)] for _ in range(n)]  # 플레이어 맵
ps = [None] * (m + 1)  # 플레이어 리스트

#  상,우,하,좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for x in range(n):
    row = list(map(int, input().split()))
    for y, ele in enumerate(row):
        if ele == 0: continue
        a[x][y].append(ele)

for no in range(1, m + 1):
    x, y, d, s = map(int, input().split())
    x -= 1
    y -= 1
    p = Player(no, x, y, d, s)
    ps[no]=p
    b[x][y].append(no)

def inBoard(nx, ny):
    if 0 <= nx < n and 0 <= ny < n:
        return True
    return False

def changeDirection(d):
    return (d + 1) % 4

def move(p, x, y, nx, ny):
    global b

    p.x, p.y = nx, ny
    b[nx][ny].append(p.no)
    b[x][y].remove(p.no)

def drop(p, x, y):
    global a

    a[x][y].append(p.g)
    p.g = 0

def get(p, x, y):
    global a

    a[x][y].sort(reverse=True)
    p.g = a[x][y][0]
    a[x][y].remove(p.g)

def fight(p1, p2):
    # 해당 플레이어의 초기 능력치와 가지고 있는 총의 공격력의 합을 비교하여 더 큰 플레이어가 이기게 됩니다.
    if p1.s + p1.g > p2.s + p2.g:
        winner = p1
        loser = p2
    elif p1.s + p1.g < p2.s + p2.g:
        winner = p2
        loser = p1
    # 만일 이 수치가 같은 경우에는 플레이어의 초기 능력치가 높은 플레이어가 승리하게 됩니다.
    else:
        if p1.s > p2.s:
            winner = p1
            loser = p2
        else:
            winner = p2
            loser = p1
    # 이긴 플레이어는 각 플레이어의 초기 능력치와 가지고 있는 총의 공격력의 합의 차이만큼을 포인트로 획득하게 됩니다.
    winner.p += (winner.s + winner.g) - (loser.s + loser.g)

    return [winner, loser]

def lose(p):
    x, y, d = p.x, p.y, p.d
    # 진 플레이어는 본인이 가지고 있는 총을 해당 격자에 내려놓고,
    if p.g!=0:
        drop(p, x, y)
    # 해당 플레이어가 원래 가지고 있던 방향대로 한 칸 이동합니다.
    nx, ny = x + dx[d], y + dy[d]
    # 만약 이동하려는 칸에 다른 플레이어가 있거나 격자 범위 밖인 경우에는 오른쪽으로 90도씩 회전하여 빈 칸이 보이는 순간 이동합니다.
    while True:
        if inBoard(nx, ny) and len(b[nx][ny]) == 0:
            break
        d = changeDirection(d)
        nx, ny = x + dx[d], y + dy[d]
    p.d = d
    move(p, x, y, nx, ny)
    # 만약 해당 칸에 총이 있다면, 해당 플레이어는 가장 공격력이 높은 총을 획득하고 나머지 총들은 해당 격자에 내려 놓습니다.
    if len(a[p.x][p.y]) > 0:
        get(p, p.x, p.y)

def win(p):
    # 이긴 플레이어는 승리한 칸에 떨어져 있는 총들과 원래 들고 있던 총 중 가장 공격력이 높은 총을 획득하고,
    # 나머지 총들은 해당 격자에 내려 놓습니다.
    drop(p, p.x, p.y)
    get(p, p.x, p.y)

for round in range(1, K + 1):
    # 전체 과정
    # 첫 번째 플레이어부터 순차적으로 본인이 향하고 있는 방향대로 한 칸만큼 이동합니다.
    for p in ps[1:]:
        x, y, d = p.x, p.y, p.d
        nx, ny = x + dx[d], y + dy[d]
        # 만약 해당 방향으로 나갈 때 격자를 벗어나는 경우에는 정반대 방향으로 방향을 바꾸어서
        if not inBoard(nx, ny):
            d = (d+2)%4
            nx, ny = x + dx[d], y + dy[d]
            p.d = d
        # 1만큼 이동합니다.
        move(p, x, y, nx, ny)
        # 만약 이동한 방향에 플레이어가 없다면
        if len(b[p.x][p.y]) == 1:
            # move(p, x, y, nx, ny)
            # 해당 칸에 총이 있는지 확인합니다.
            if len(a[p.x][p.y]) > 0:
                # 플레이어가 이미 총을 가지고 있는 경우에는 놓여있는 총들과 플레이어가 가지고 있는 총 가운데 공격력이 더 쎈 총을 획득하고, 나머지 총들은 해당 격자에 둡니다.
                if p.g != 0:
                    drop(p, p.x, p.y)
                # 총이 있는 경우, 해당 플레이어는 총을 획득합니다.
                get(p, p.x, p.y)
        # 만약 이동한 방향에 플레이어가 있는 경우에는 두 플레이어가 싸우게 됩니다.
        else:
            winner, loser = fight(ps[b[p.x][p.y][0]], ps[b[p.x][p.y][1]])
            lose(loser)
            win(winner)

answer = []
for p in ps[1:]:
    answer.append(p.p)
print(*answer)

v1(2023.03.29)

import sys
input=sys.stdin.readline

n,m,k=map(int,input().split())
pmap=[[[] for _ in range(n)] for _ in range(n)] # 플레이어들의 맵
gmap=[[[] for _ in range(n)] for _ in range(n)] # 총들의 맵
pos=[] # 플레이어들의 위치 배열
points=[] # 플레이어들의 포인트 배열

class Player: # 플레이어 클래스
    def __init__(self,no,x,y,d,s,g=0):
        self.no=no
        self.x=x
        self.y=y
        self.d=d
        self.s=s
        self.g=g

dx=[-1,0,1,0]
dy=[0,1,0,-1]

for i in range(n):
    row=list(map(int,input().split()))
    for j in range(n):
        gmap[i][j].append(row[j])

for no in range(m):
    x,y,d,s=map(int,input().split())
    x,y=x-1,y-1
    pos.append([x,y])
    pmap[x][y].append(Player(no,x,y,d,s))
    points.append(0)

# 이동한다.
def move(nx,ny,player):
    global pmap,pos
    # 플레이어의 위치를 업데이트한다.
    pmap[nx][ny].append(player)
    pmap[player.x][player.y].remove(player)
    player.x,player.y=nx,ny
    pos[player.no]=[player.x,player.y]
    return player
# 총을 잃는다.
def lose(x,y,player):
    global gmap
    if player.g!=0:
        gmap[x][y].append(player.g)
    player.g=0
    return player
# 총을 줍는다.
def get(x,y,player):
    global gmap
    # 총을 잃은 플레이어가
    lost_player=lose(x,y,player)
    # 가장 공격력이 높은 총을
    tg=max(gmap[x][y])
    # 장착한다.
    lost_player.g=tg
    # 해당 총은 총 맵에서 없앤다.
    gmap[x][y].remove(tg)
    return lost_player

for _ in range(k):
    # 각 플레이어들이 각자의 위치에서 순서대로
    for ax,ay in pos:
        # 이번 플레이어
        me=pmap[ax][ay][0]
        # 정면의 칸으로
        me_nx=ax+dx[me.d]
        me_ny=ay+dy[me.d]
        # 만약 정면의 칸이 범위 밖이면, 정반대 방향의 칸으로
        if not (0<=me_nx<n and 0<=me_ny<n):
            me.d=(me.d+2)%4
            me_nx=ax+dx[me.d]
            me_ny=ay+dy[me.d]
        # 이동
        me = move(me_nx, me_ny, me)
        # 만약 이동한 칸에 이번 플레이어만 있다면
        if pmap[me_nx][me_ny][0]==me:
            # 해당 칸에 총이 있다면
            if len(gmap[me.x][me.y])>=1:
                # 총을 줍는다.
                me=get(me.x,me.y,me)
        # 다른 플레이어가 있다면
        else:
            bx,by=me.x,me.y
            # 상대 플레이어
            other=pmap[bx][by][0]
            # (초기 능력치 + 총의 공격력, 초기 능력치) 순으로 우선순위를 매겨 비교합니다.
            me_sum=me.s+me.g
            other_sum=other.s+other.g
            if me_sum>other_sum:
                winner=me
                loser=other
            elif me_sum<other_sum:
                winner=other
                loser=me
            else:
                if me.s>other.s:
                    winner=me
                    loser=other
                else:
                    winner=other
                    loser=me
            # 이기면 포인트를 얻게 됩니다.
            points[winner.no]+=abs(me_sum-other_sum)
            # 패자는 총을 잃고
            loser=lose(loser.x,loser.y,loser)
            # 다음으로 갈 칸을 선택하는데
            loser_nx,loser_ny=loser.x+dx[loser.d],loser.y+dy[loser.d]
            # 만약 이동하려는 칸에 다른 플레이어가 있거나 격자 범위 밖인 경우에는 오른쪽으로 90도씩 회전하여 빈 칸이 보이면
            if not (0<=loser_nx<n and 0<=loser_ny<n) or len(pmap[loser_nx][loser_ny])!=0:
                while True:
                    loser.d=(loser.d+1)%4
                    loser_nx,loser_ny=loser.x+dx[loser.d],loser.y+dy[loser.d]
                    if (0<=loser_nx<n and 0<=loser_ny<n) and len(pmap[loser_nx][loser_ny])==0:
                        break
            # 이동합니다
            loser=move(loser_nx,loser_ny,loser)
            # 패자가 이동한 칸에 총이 있다면
            if len(gmap[loser.x][loser.y])>=1:
                # 줍는다.
                loser=get(loser.x,loser.y,loser)
            # 승자의 칸에 총이 있다면
            if len(gmap[winner.x][winner.y]) >= 1:
                # 줍는다.
                winner=get(bx,by,winner)
print(*points)