백준 / 17135 / 캐슬 디펜스 / 파이썬, python, pypy

17135번: 캐슬 디펜스

문제를 읽고 적이 아래로 한칸 이동한다를 "궁수가 한칸씩 위로 이동한다" 라고 생각하였다.

(board 자체를 수정하지 않고, 궁수 배열을 따로 관리하며 row를 바꾸는것이 더 간단하다고 생각하였기 때문)

 

로직은

1. 궁수 3명의 index(column)를 정하여 archer 배열로 선언한다 (조합)

2. archer의 row를 N+1부터 1까지 (역순으로) 변경하며 가장 가까운 적을 제거한다.

    2-1. archer의 좌표가 (r, c)라면 (r-1, c)부터 좌, 우, 상 방향으로 이동하며 distance를 1씩 증가시키며 bfs를 실행한다.

    2-2. 가장 가까운 적의 좌표를 current enemy set에 저장한다.

    2-3. 3명의 archer 모두 탐색한 뒤 current enemy set에 있는 좌표를 통해 board를 변경한다 (board[x][y] = 1)

    2-4. current enemy set을 enemy set과 합친다.

    2-4. r을 하나 감소시키고 (궁수를 한칸 전진 시키고) 2-1부터 다시 시작한다.

3. enemy set에 있는 좌표를 통해 board를 변경한다. (board[x][y] = 0, 죽은 적을 되살린다.)

4. enemy set의 길이를 return한다.

 

import sys
from collections import deque
 
direction = ((0, -1), (0, 1), (-1, 0))
 
def bfs(r, c):
    queue = deque([(1, r-1, c)])
    visit = set()
    visit.add((r-1, c))
 
    min_distance = float('inf')
    min_x, min_y = -1, -1
 
    while queue:
        d, x, y = queue.popleft()
 
        if min_distance < d: break
        if board[x][y] == 1:
            if min_distance == float('inf'):
                min_distance = d
                min_x, min_y = x, y
            else:
                if min_y > y:
                    min_x, min_y = x, y
 
        if d == D: continue
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < N and 0 <= ny < M): continue
            if (nx, ny) in visit: continue
            queue.append((d+1, nx, ny))
            visit.add((nx, ny))
 
    return (min_x, min_y)
 
 
def attack_simulation(archer):
    dead_enemy = set()
 
    for archer_row in range(N, 0, -1):
        cur_dead_enemy = set()
        for archer_col in archer:
            near_enemy = bfs(archer_row, archer_col)
            if near_enemy == (-1, -1): continue
            cur_dead_enemy.add(near_enemy)
        for x, y in cur_dead_enemy:
            board[x][y] = 0
        dead_enemy |= cur_dead_enemy
 
    cnt_dead_enemy = len(dead_enemy)
    for x, y in dead_enemy:
        board[x][y] = 1
 
    return cnt_dead_enemy
 
def solve():
    answer = 0
    
    archer = []
    for a in range(M):
        archer.append(a)
        for b in range(a+1, M):
            archer.append(b)
            for c in range(b+1, M):
                archer.append(c)
                answer = max(answer, attack_simulation(archer))
                archer.pop()
            archer.pop()
        archer.pop()
 
    return answer
 
 
N, M, D = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
 
print(solve())