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

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/royal-knight-duel/description

코딩테스트 기출 문제 설명: 왕실의 기사 대결 | 코드트리

 

from collections import deque

# 방향: 상(0), 우(1), 하(2), 좌(3)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 입력 처리
L, N, Q = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(L)]
knight_board = [[0] * L for _ in range(L)]  # 기사 위치 저장
knight_info = [None]  # 기사 정보: (r, c, h, w, k)
knight_damage = [0] * (N + 1)  # 기사별 피해 저장

# 기사 정보 입력 및 초기화
for knight_id in range(1, N + 1):
    r, c, h, w, k = map(int, input().split())
    r, c = r - 1, c - 1
    knight_info.append((r, c, h, w, k))
    for i in range(r, r + h):
        for j in range(c, c + w):
            knight_board[i][j] = knight_id

# 체스판 범위 체크
def is_range(r, c):
    return 0 <= r < L and 0 <= c < L

# 기사 이동 가능 여부 확인 (BFS)
def can_move_knight(knight_id, direction):
    if knight_info[knight_id][4] <= 0:  # 체력 0 이하면 이동 불가
        return False, [], []
    
    r, c, h, w, _ = knight_info[knight_id]
    q = deque()
    movable_coords = []  # (knight_id, x, y)
    affected_knights = [knight_id]  # 이동에 영향을 받는 기사 번호
    visited = [[False] * L for _ in range(L)]
    
    # 초기 기사 위치 큐에 추가
    for i in range(r, r + h):
        for j in range(c, c + w):
            visited[i][j] = True
            q.append((i, j))
            movable_coords.append((knight_id, i, j))
    
    while q:
        x, y = q.popleft()
        nr, nc = x + dx[direction], y + dy[direction]
        
        if not is_range(nr, nc):  # 체스판 밖
            return False, [], []
        if visited[nr][nc]:  # 이미 방문
            continue
        if board[nr][nc] == 2:  # 벽
            return False, [], []
        
        current_knight = knight_board[nr][nc]
        if current_knight == knight_id:  # 같은 기사 영역
            q.append((nr, nc))
            movable_coords.append((knight_id, nr, nc))
            visited[nr][nc] = True
        elif current_knight != 0 and current_knight not in affected_knights:  # 다른 기사 영역
            affected_knights.append(current_knight)
            r1, c1, h1, w1, _ = knight_info[current_knight]
            for i in range(r1, r1 + h1):
                for j in range(c1, c1 + w1):
                    if not visited[i][j]:
                        q.append((i, j))
                        movable_coords.append((current_knight, i, j))
                        visited[i][j] = True
    
    return True, movable_coords, affected_knights

# 기사들 이동
def move_knights(coords, affected_knights, direction):
    tmp_board = [[0] * L for _ in range(L)]
    for i in range(L):
        for j in range(L):
            if knight_board[i][j] not in affected_knights:
                tmp_board[i][j] = knight_board[i][j]
    
    # 새 위치로 이동
    for knight_id, x, y in coords:
        nx, ny = x + dx[direction], y + dy[direction]
        tmp_board[nx][ny] = knight_id  # 오류 수정: nr, nc -> nx, ny
    
    # knight_board 업데이트
    for i in range(L):
        for j in range(L):
            knight_board[i][j] = tmp_board[i][j]

# 기사 위치 정보 업데이트
def update_knight_positions():  
    for knight_id in range(1, N + 1):
        r, c, h, w, k = knight_info[knight_id]
        if k <= 0:
            continue
        found = False
        for i in range(L):
            for j in range(L):
                if knight_board[i][j] == knight_id:
                    knight_info[knight_id] = (i, j, h, w, k)
                    found = True
                    break
            if found:
                break

# 피해 계산
def apply_damage(affected_knights, origin_knight):
    for i in range(L):
        for j in range(L):
            knight_id = knight_board[i][j]
            if knight_id == 0 or knight_id == origin_knight or knight_id not in affected_knights:
                continue
            if board[i][j] == 1:  # 함정
                r, c, h, w, k = knight_info[knight_id]
                k -= 1
                knight_damage[knight_id] += 1
                knight_info[knight_id] = (r, c, h, w, k)
                if k <= 0:
                    for i2 in range(r, r + h):
                        for j2 in range(c, c + w):
                            knight_board[i2][j2] = 0

# 살아있는 기사들의 총 피해 계산
def get_total_damage():
    total = 0
    for knight_id in range(1, N + 1):
        _, _, _, _, k = knight_info[knight_id]
        if k > 0:
            total += knight_damage[knight_id]  
    return total

# 명령 처리
for _ in range(Q):
    knight_id, direction = map(int, input().split())
    possible, coords, affected_knights = can_move_knight(knight_id, direction)
    if possible:
        move_knights(coords, affected_knights, direction)
        update_knight_positions()  # 오류 수정: 함수 이름 오타 수정
        apply_damage(affected_knights, knight_id)

# 결과 출력
print(get_total_damage())