[CodeTree] 싸움땅 - 삼성 SW 역량테스트 2022 하반기 오전 1번 문제

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

 

문제 분석

• NxN 크기의 격자에서 각 플레이어 간 싸움이 진행됨.
• 초기 각각의 좌표에는 무기들이 있을 수 있으며, 초기 Player가 위치한 좌표에는 무기가 존재하지 않음.
• Player는 (x좌표, y좌표, 방향, 초기 능력치)가 입력으로 주어짐.
• Player 이동
  • 첫 번째 Player부터 순차적으로 본인의 방향으로 1칸 이동.
  • 이동하는 영역이 NxN 격자를 벗어나면, 정반대 방향으로 방향을 변경하여 1만큼 이동.
• 이동한 방향에 Player가 없는 경우
  • 해당 칸에 총이 있는지 확인.
  • 총이 있을 경우, 현재 Player가 가지고 있는 총보다 높은 공격력을 가진 총이랑 변경.
• 이동한 방향에 Player가 있는 경우
  • 싸움 시작
    • 각 Player의 (초기 능력치 + 총의 공격력)이 크면 싸움에서 이김.
    • 만약 동일하다면, 초기 능력치가 큰 Player가 이김.
    • 두 Player 간 (초기 능력치 + 총의 공격력) 차이를 이긴 Player가 점수를 획득함.
  • 진 Player
    • 자신이 가지고 있는 총을 현재 좌표에 내려둔 후, 원래 이동 방향으로 한 칸 이동함.
    • 이동하려는 위치가 격자를 벗어나거나 다른 player가 존재한다면, 오른쪽으로 90' 회전하고 빈 칸이 존재할 경우 즉시 이동.
    • 이동 한 칸에 총이 존재할 경우, 가장 공격력이 높은 총을 진 Player가 획득함.
  • 이긴 Player
    • 현재 격자에 있는 총 중 이긴 Player의 총보다 공격력이 높은 총이 있으면 교체함.
• K Turn동안 시뮬레이션을 수행한 후, 각 플레이어가 얻은 점수를 pid 순서대로 Return하는 문제.

 

소스 코드

# define lib
from collections import defaultdict

# set value from input
n, m, k = map(int, input().split())
direc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
guns, player_pos = defaultdict(list), defaultdict(list)
player_info, player_score = defaultdict(list), [0]*(m+1)

for i in range(n):
    line = list(map(int, input().split()))
    for j in range(n):
        guns[(i, j)].append(line[j])
    
for i in range(1, m+1):
    px, py, pd, p_stat = map(int, input().split())
    player_pos[i] = [px-1, py-1, pd]
    player_info[i] = [p_stat, p_stat, 0] # total, init_stat, gun

turn = 0
while turn < k:
    # player move
    for pid in range(1, m+1):
        px, py, pd = player_pos[pid]
        nx, ny = px+direc[pd][0], py+direc[pd][1]
        
        # change pd and update player_pos
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            pd = (0 if pd == 2 else 2) if pd in [0, 2] else (1 if pd == 3 else 3)
            nx, ny = px+direc[pd][0], py+direc[pd][1]
        player_pos[pid] = [nx, ny, pd]
        # print(player_pos)

        # find another player which has (nx,  ny) pos
        fpid = None
        for npid in range(1, m+1):
            if pid == npid:
                continue
            if (nx, ny) == tuple(player_pos[npid][:2]):
                fpid = npid
                break

        # not find (unique)
        if fpid is None:
            if guns[(nx, ny)] and guns[(nx, ny)][-1] > player_info[pid][2]:
                player_info[pid][2], guns[(nx, ny)][-1] = guns[(nx, ny)][-1], player_info[pid][2]
                player_info[pid][0] = player_info[pid][1] + player_info[pid][2]
                guns[(nx, ny)].sort()

        # find (fight)
        else:
            _candits = [(pid, *player_info[pid]), (fpid, *player_info[fpid])]
            _candits.sort(key=lambda x: (-x[1], -x[2])) # total, init_stat

            # winner / loser and update score
            wpid, lpid = _candits[0][0], _candits[1][0]
            player_score[wpid] += player_info[wpid][0] - player_info[lpid][0]

            # remove loser's gun
            if player_info[lpid][2] > 0:
                guns[(nx, ny)].append(player_info[lpid][2])
                guns[(nx, ny)].sort()
                player_info[lpid][0] -= player_info[lpid][2]
                player_info[lpid][2] = 0

            # update loser's pos
            lx, ly, ld = player_pos[lpid]
            next_l_pos = []
            for cnt in range(4):
                nlx, nly = lx+direc[(ld+cnt)%4][0], ly+direc[(ld+cnt)%4][1]
                if nlx < 0 or nlx >= n or nly < 0 or nly >= n:
                    continue
                
                p_flag = True
                for nnpid in range(1, m+1):
                    if (nlx, nly) == tuple(player_pos[nnpid][:2]):
                        p_flag = False
                        break

                if p_flag:
                    next_l_pos.append([nlx, nly, (ld+cnt)%4])
                    break
            
            # check loser can move
            if len(next_l_pos) > 0:
                nlx, nly, nld = next_l_pos[0]
                player_pos[lpid] = [nlx, nly, nld]
                if guns[(nlx, nly)]:
                    player_info[lpid][2] = guns[(nlx, nly)].pop()
                    player_info[lpid][0] = player_info[lpid][1] + player_info[lpid][2]

            # winner
            player_pos[wpid][0], player_pos[wpid][1] = nx, ny
            if guns[(nx, ny)] and guns[(nx, ny)][-1] > player_info[wpid][2]:
                player_info[wpid][2], guns[(nx, ny)][-1] = guns[(nx, ny)][-1], player_info[wpid][2]
                player_info[wpid][0] = player_info[wpid][1] + player_info[wpid][2]
                guns[(nx, ny)].sort()
    turn += 1
print(*player_score[1:])

• 제출 횟수: 2회 (싸움에서 진 Player의 총을 버리는 작업은 진행했지만, total_stat 갱신 작업을 수행하지 않음)
• 풀이 시간: 65분