[코드트리/삼성SW역량테스트] 왕실의 기사 대결 (Python)

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/royal-knight-duel

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

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:31:25

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

구현 문제.

 

1. BFS를 쓰라고 대놓고 요구하는 문제. 어떤 기사가 이동했을 때, 영향을 받는 기사들 및 그 하위 기사들 모두가 이동 가능한 상태여야 한다. 즉 모든 기사에 대해 탐색을 수행하고, 만약 이동 가능하다면 그 때 전부 업데이트해야 한다.

 

2. 기사가 이동할 때 대미지는 밀쳐진 기사들만이 해당된다는 점을 유의하자.

 

풀이 코드

import sys
input = sys.stdin.readline

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

L, N, Q = map(int, input().split())
chess_map = [list(map(int, input().split())) for _ in range(L)]
knight_map = [[-1]*L for _ in range(L)]
knight_list = list()

class Knight() :
    def __init__(self, r, c, h, w, k, idx) :
        self.r = r
        self.c = c
        self.h = h
        self.w = w
        self.idx = idx

        self.life = k
        self.maxlife = k
        self.dead = False
        for i in range(r, r+h) :
            for j in range(c, c+w) :
                knight_map[i][j] = idx
    
    def is_movable(self, d) :
        if self.dead :
            return False
        
        self._r = self.r + dr[d]
        self._c = self.c + dc[d]
        self.other_set = set()
        for i in range(self._r, self._r + self.h) :
            for j in range( self._c,  self._c + self.w) :
                if not (-1 < i < L and -1 < j < L) or chess_map[i][j] == 2 :
                    return False
                if knight_map[i][j] > -1 and self.idx != knight_map[i][j] :
                    self.other_set.add(knight_map[i][j])
        
        tmp = True
        for other in self.other_set :
            tmp &= knight_list[other].is_movable(d)
        return tmp

    def move(self, hurt = False) :
        self.r = self._r
        self.c = self._c
        for other in self.other_set :
            knight_list[other].move(hurt = True)
        if hurt :
            self.hurt()
    
    def hurt(self) :
        for i in range(self.r, self.r + self.h ) :
            for j in range(self.c, self.c + self.w ) :
                if chess_map[i][j] == 1 :
                    self.life -= 1
        if self.life <= 0 :
            self.life = 0
            self.dead = True

    def damage(self) :
        if self.dead :
            return 0
        return self.maxlife - self.life

def update_knight_map() :
    global knight_map
    knight_map = [[-1]*L for _ in range(L)]
    for knight in knight_list :
        if knight.dead :
            continue
        for i in range(knight.r, knight.r + knight.h ) :
            for j in range(knight.c, knight.c + knight.w ) :
                knight_map[i][j] = knight.idx

for i in range(N) :
    r, c, h, w, k = map(int, input().split())
    knight_list.append(Knight(r-1, c-1, h, w, k, i))

for _ in range(Q) :
    i, d = map(int, input().split())
    if knight_list[i-1].is_movable(d) :
        knight_list[i-1].move()
        update_knight_map()
        
ans = 0
for knight in knight_list :
    ans += knight.damage()
print(ans)

풀이 완료!