문제 링크

https://www.acmicpc.net/problem/17135

문제 설명

• 적들이 성벽으로 한 칸씩 내려옴
• 궁수들이 적들을 쏨
• 궁수 3명를 배치하여 잡을 수 있는 적 수의 최댓값 구하기

풀이

• combinations로 배치할 수 있는 모든 경우의 수를 찾는다
• 모든 경우에 대해
• BFS로 궁수 별 가장 가까운 왼쪽의 적을 찾는다
• board에서 제거 및 카운트
• 적들이 한 칸 내려옴 (성벽을 올림)
• 성벽이 끝에 다다를 때까지 반복

BFS 구현

• 좌, 상, 우 순서로 세 가지 방향만 append
• 노드에 거리를 함께 저장해, 사거리 이상일 경우 return empty
• 사거리 이내의 적이 없으면 return empty

예상 시간복잡도

• 브루트 포스 : 15 Combination 3
• 모든 row 반복 : O(N)
• BFS : O(N x M + 4 x (N x M)) = O(N x M)

느낀 점

• 처음 궁수들이 적 한 명을 동시에 맞출 수 있다는 문구를 보지 못해서 좀 헤맸다.

코드

from itertools import combinations
from collections import deque


def init():
    import sys
    ipt = sys.stdin.readline
    h, w, d = map(int, ipt().split())
    origin_board = [list(map(int, ipt().split())) for _ in range(h)]
    dy = [0, -1, 0]
    dx = [-1, 0, 1]
    return w, h, origin_board, -1, dy, dx, d


def bfs(start):
    sy, sx = start
    visited = [[False] * w for _ in range(h)]
    visited[sy][sx] = True
    q = deque()
    q.append((sy, sx, 1))
    while q:
        cy, cx, cd = q.popleft()
        if cd > d:
            return
        if board[cy][cx] == 1:
            return (cy, cx)
        for i in range(3):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny, nx, cd+1))


w, h, origin_board, ans, dy, dx, d = init()
for x1, x2, x3 in combinations(range(w), 3):
    board = [origin_board[i][:] for i in range(h)]
    count = 0
    floor = h
    while floor:
        enemy_list = [
            bfs((floor-1, x1)),
            bfs((floor-1, x2)),
            bfs((floor-1, x3)),
        ]
        for enemy in enemy_list:
            if enemy:
                ey, ex = enemy
                if board[ey][ex]:
                    board[ey][ex] = 0
                    count += 1
        floor -= 1
    ans = max(ans, count)
print(ans)