[CodeTree] 왕실의 기사 대결 - 삼성 SW 역량테스트 2023 하반기 오후 1번 문제

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

 

문제 분석

• LxL 크기의 체스판 위에서 기사들이 대결을 하기 위해 준비하고 있음.
• 모든 기사들은 자신의 마력을 활용해 상대방 기사를 밀쳐낼 수 있으며, (r,c)를 기준으로 (r+h, c+w)까지 특정 기사의 영역이 됨.
• 기사는 초기 체력을 K만큼 가지고 있으며, 0이하의 체력이 될 경우 게임에서 제외됨.
• 기사 이동
  • 명령받은 기사는 상하좌우 중 한 방향으로 한 칸 이동할 수 있음.
  • 이동하려는 위치에 다른 기사가 있을 경우, 연쇄적으로 함께 이동하게 됨.
  • 이동하려는 방향에 벽이 있거나 격자를 벗어나는 경우, 따로 이동하지 않고 그대로 턴을 종료함
• 대결 데미지
  • 명령받은 기사가 다른 기사를 밀치게 되었을 때 피해를 입게 됨.
  • 각 기사들은 해당 기사가 속한 영역 중 함정이 있는 칸 수 만큼 체력이 감소하며, 0이하가 되면 게임에서 사라짐.
  • 명령받은 기사는 움직여도 따로 피해를 입지 않으며, 밀쳐졌더라도 함정이 없으면 피해를 입지 않음.
• Q번의 명령 후 생존한 기사들이 받은 총 데미지의 합을 Return하는 문제.

 

문제 접근

• 초기화 단계
  • 빈칸 / 벽 / 함정을 나타내기 위한 field 배열과, 기사의 위치를 저장하기 위한 knights_field 배열을 선언하여 따로 관리.
  • 매 번 명령할 때마다 움직이려고 하는 기사를 찾는 것은 비효율적이기 때문에, 기사의 영역 중 좌측 상단 지점을 저장하여 이를 갱신하며 관리 (명령 시작시 O(1)로 가능).
• 기사 움직임
  • 명령받은 기사의 시작 지점으로 하여 연쇄적으로 움직여야하는 그룹을 찾는 과정을 BFS로 진행.
  • 진행할 때 현재 탐색하고자 하는 격자의 기사 pid와 이동하려고자 하는 격자의 기사 pid가 같을 경우, 쿼리로 주어진 이동방향 뿐만 아니라, 4방향 모두로 이동 가능 (하나의 그룹을 모두 찾는다는 의미).
  • pid가 다른 경우, 쿼리로 주어진 이동방향에 한하여 연결되었다면 (아래 방향이 주어졌을 때, 아래로 밀리면 같이 움직이는 그룹인 경우), queue에 넣어 계속 탐색을 수행.
  • 수행 후 기사의 시작 위치, 그룹 위치, 체력을 갱신하는 작업을 수행.

 

소스 코드

# define lib
from copy import deepcopy
from collections import deque

# set value from input
L, N, Q = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(L)]
knights_field = [[0]*L for _ in range(L)]
knights_spt, knights_hp, origin_knights_hp = dict(), dict(), dict()
direc = [(-1, 0), (0, 1), (1, 0), (0, -1)]

for pid in range(1, N+1):
    r1, c1, h, w, k = map(int, input().split())
    knights_spt[pid], knights_hp[pid], origin_knights_hp[pid] = (r1-1, c1-1), k, k
    for i in range(r1-1, r1-1+h):
        for j in range(c1-1, c1-1+w):
            knights_field[i][j] = pid

# queries
for _ in range(Q):
    kpid, kd = map(int, input().split())
    kx, ky = knights_spt[kpid]
    dq, visit = deque([(kx, ky, knights_field[kx][ky])]), {(kx, ky)}
    groups, group_id = [(kx, ky)], {knights_field[kx][ky]}
    
    # find cascade group
    while dq:
        cx, cy, cgroup_num = dq.popleft()
        for didx in range(0, 4):
            nx, ny = cx+direc[didx][0], cy+direc[didx][1]
            if nx < 0 or nx >= L or ny < 0 or ny >= L or (nx, ny) in visit or field[nx][ny] == 2:
                continue
            # same group
            if knights_field[nx][ny] == cgroup_num:
                visit.add((nx, ny))
                groups.append((nx, ny))
                dq.append((nx, ny, cgroup_num))
            # another group
            elif knights_field[nx][ny] > 0 and knights_field[nx][ny] != cgroup_num and kd == didx:
                visit.add((nx, ny))
                groups.append((nx, ny))
                group_id.add(knights_field[nx][ny])
                dq.append((nx, ny, knights_field[nx][ny]))

    # check move
    flag = True
    for gx, gy in groups:
        nx, ny = gx+direc[kd][0], gy+direc[kd][1]
        if nx < 0 or nx >= L or ny < 0 or ny >= L or field[nx][ny] == 2:
            flag = False
            break
    
    # can not move
    if not flag:
        continue

    # copy field
    new_knights_field = deepcopy(knights_field)
    for gx, gy in groups:
        new_knights_field[gx][gy] = 0

    # move and damage
    for gx, gy in groups:
        nx, ny = gx+direc[kd][0], gy+direc[kd][1]
        new_knights_field[nx][ny] = knights_field[gx][gy]
        if field[nx][ny] == 1 and knights_field[gx][gy] != kpid:
            knights_hp[knights_field[gx][gy]] -= 1

    # check hp and update
    for gpid in group_id:
        bx, by = knights_spt[gpid]
        if knights_hp[gpid] > 0 :
            knights_spt[gpid] = (bx+direc[kd][0], by+direc[kd][1])
        else:
            dq = deque([(bx, by)])
            while dq:
                cx, cy = dq.popleft()
                new_knights_field[cx][cy] = 0
                for didx in range(0, 4):
                    nx, ny = cx+direc[didx][0], cy+direc[didx][1]
                    if nx < 0 or nx >= L or ny < 0 or ny >= L or new_knights_field[nx][ny] != gpid:
                        continue
                    dq.append((nx,ny))
            knights_spt[gpid] = (-1, -1)
    knights_field = new_knights_field

score = 0
for key in origin_knights_hp.keys():
    if knights_hp[key] > 0:
        score += origin_knights_hp[key] - knights_hp[key]
print(score)

• 제출 횟수: 1회
• 풀이 시간: 40분