[코드트리] - 왕실의 기사 대결

출처 : https://www.codetree.ai/training-field/frequent-problems/problems/royal-knight-duel/description?page=2&pageSize=5

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

 

왕실의 기사들은 L×L 크기의 체스판 위에서 대결을 준비하고 있습니다. 체스판의 왼쪽 상단은 (1,1)로 시작하며, 각 칸은 빈칸, 함정, 또는 벽으로 구성되어 있습니다. 체스판 밖도 벽으로 간주합니다.

왕실의 기사들은 자신의 마력으로 상대방을 밀쳐낼 수 있습니다. 각 기사의 초기위치는 (r,c)로 주어지며, 그들은 방패를 들고 있기 때문에 (r,c)를 좌측 상단으로 하며 h(높이)×w(너비) 크기의 직사각형 형태를 띄고 있습니다. 각 기사의 체력은 k로 주어집니다.

(1) 기사 이동

왕에게 명령을 받은 기사는 상하좌우 중 하나로 한 칸 이동할 수 있습니다. 이때 만약 이동하려는 위치에 다른 기사가 있다면 그 기사도 함께 연쇄적으로 한 칸 밀려나게 됩니다. 그 옆에 또 기사가 있다면 연쇄적으로 한 칸씩 밀리게 됩니다. 하지만 만약 기사가 이동하려는 방향의 끝에 벽이 있다면 모든 기사는 이동할 수 없게 됩니다. 또, 체스판에서 사라진 기사에게 명령을 내리면 아무런 반응이 없게 됩니다.

(2) 대결 대미지

명령을 받은 기사가 다른 기사를 밀치게 되면, 밀려난 기사들은 피해를 입게 됩니다. 이때 각 기사들은 해당 기사가 이동한 곳에서 w×h 직사각형 내에 놓여 있는 함정의 수만큼만 피해를 입게 됩니다. 각 기사마다 피해를 받은 만큼 체력이 깎이게 되며, 현재 체력 이상의 대미지를 받을 경우 기사는 체스판에서 사라지게 됩니다. 단, 명령을 받은 기사는 피해를 입지 않으며, 기사들은 모두 밀린 이후에 대미지를 입게 됩니다. 밀렸더라도 밀쳐진 위치에 함정이 전혀 없다면 그 기사는 피해를 전혀 입지 않게 됨에 유의합니다.

Q 번에 걸쳐 왕의 명령이 주어졌을 때, Q 번의 대결이 모두 끝난 후 생존한 기사들이 총 받은 대미지의 합을 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 L, N, Q가 공백을 사이에 두고 주어집니다.

다음 L 개의 줄에 걸쳐서 L×L 크기의 체스판에 대한 정보가 주어집니다.

• 0이라면 빈칸을 의미합니다.
• 1이라면 함정을 의미합니다.
• 2라면 벽을 의미합니다.

다음 N 개의 줄에 걸쳐서 초기 기사들의 정보가 주어집니다. 이 정보는 (r,c,h,w,k) 순으로 주어지며, 이는 기사의 처음 위치는 (r,c)를 좌측 상단 꼭지점으로 하며 세로 길이가 h, 가로 길이가 w인 직사각형 형태를 띄고 있으며 초기 체력이 k라는 것을 의미합니다. 입력은 1번 기사부터 N번 기사까지 순서대로 정보가 주어집니다.

단, 처음 주어지는 기사들의 위치는 기사들끼리 서로 겹쳐져 있지 않습니다. 또한 기사와 벽은 겹쳐서 주어지지 않습니다.

다음 Q 개의 줄에 걸쳐 왕의 명령에 대한 정보가 주어집니다. 이 정보는 (i,d) 형태로 주어지며 이는 i번 기사에게 방향 d로 한 칸 이동하라는 명령임을 뜻합니다. i는 1 이상 N 이하의 값을 갖으며, 이미 사라진 기사 번호가 주어질 수도 있음에 유의합니다. d는 0, 1, 2, 3 중에 하나이며 각각 위쪽, 오른쪽, 아래쪽, 왼쪽 방향을 의미합니다.

• L: 체스판의 크기 (3≤L≤40)
• N: 기사의 수 (1≤N≤30)
• Q: 명령의 수 (1≤Q≤100)
• k: 기사의 체력 (1≤k≤100)

출력 형식

Q 개의 명령이 진행된 이후, 생존한 기사들이 총 받은 대미지의 합을 출력합니다.

 

l, n, q = map(int, input().split())
graph = [[2]*(l+2) for _ in range(l+2)]
board = [list(map(int, input().split())) for _ in range(l)]

# 기사들은 체스판 밖을 벗어날 수 없으므로 l+2 만큼 생성해서 바깥면은 벽(2)로 만들어준다.
for i in range(1, l+1):
    for j in range(1, l+1):
        graph[i][j] = board[i-1][j-1]

# units : 기사들의 정보, init_k : 초기 기사들의 체력 k
units = {}
init_k = [0]*(n+1)

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

for i in range(1, n+1):
    r, c, h, w, k = map(int, input().split())
    units[i] = [r, c, h, w, k]
    init_k[i] = k

def push_unit(start, dr):
    Q = []
    pset = set()
    damage = [0]*(n+1)

    Q.append(start)
    pset.add(start)

    while Q:
        cur = Q.pop(0)
        ci, cj, h, w, k = units[cur]
        
        # 현재 기사 이동
        ni = ci + dx[dr]
        nj = cj + dy[dr]

        # 만약 기사가 이동했는데 벽(2)면 함수 종료, 장애물(1) 이면 damage 1추가
        for i in range(ni, ni+h):
            for j in range(nj, nj+w):
                if graph[i][j] == 2:
                    return
                elif graph[i][j] == 1:
                    damage[cur] += 1

        # 모든 유닛에 대하여
        for idx in units:
            # 이동했거나 이미 밀려난 기사는 넘어감
            if idx in pset:
                continue
            
            ti, tj, th, tw, tk = units[idx]

            # 만약 현재 기사의 범위가 이번에 이동한 기사와 범위가 겹치면 이동하기 위해 Q와 pset에 넣기
            if ti <= ni + h -1 and ni <= ti + th -1 and tj <= nj + w -1 and nj <= tj + tw -1:
                Q.append(idx)
                pset.add(idx)

    # 맨처음 이동한 기사의 데미지는 데미지를 입지 않음
    damage[start] = 0
    
    # 이번에 이동한 기사에 대하여
    for idx in pset:
        si, sj, h, w, k = units[idx]
        # 만약 이번에 입은 데미지가 체력 k 보다 크면 아웃
        if damage[idx] >= k:
            units.pop(idx)
        
        # 그렇지 않으면 밀려난 위치로 이동하고 체력 재계산
        else:
            ni = si + dx[dr]
            nj = sj + dy[dr]
            units[idx] = [ni, nj, h, w, k-damage[idx]]


for _ in range(q):
    idx, dr = map(int, input().split())
    # 현재 살아있는 기사만 명령 수행
    if idx in units:
        push_unit(idx, dr)

answer = 0

# 결과값 계산
for idx in range(1, n+1):
    if idx in units:
        answer += init_k[idx] - units[idx][4]

# 결과값 출력
print(answer)