[백준 - Python] 17135 - 캐슬 디펜스

0.  문제 링크

 

 

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

17135번: 캐슬 디펜스

---

1.  풀이 방법

 

 

1. 다들 적군이 내려온다고 생각하는데, 나는 그냥 궁수가 올라가는 방식을 사용했다.
2. 궁수가 적을 찾는 과정은 (우선순위에 따라)BFS로 해결하였고, 적을 찾으면 적의 위치를 반환하였다.
3. 여러 궁수가 같은 적을 찾는 경우를 고려하여 적의 위치를 set으로 해결하였다.
4. 궁수의 자리는 조합을 이용하여 BF하게 해결하였다.

---

2.  코드

 

 

import sys
from itertools import combinations
from collections import deque
input = sys.stdin.readline

dir = [[0, -1], [-1, 0], [0, 1]]

def bfs(y, x):
    if maps[y][x]:      # 바로 앞에 적이 있다면 먼저 쏨, 거리가 1인 적
        return True, y, x
    else:
        visited = set()
        visited.add((y, x))

        dq = deque()
        dq.append((y, x, 1))

        while dq:
            cy, cx, dist = dq.popleft()
            for dy, dx in dir:
                ny, nx = cy + dy, cx + dx
                if 0 <= ny < n and 0 <= nx < m:
                    if (dist < d):      # d보다 거리가 짧아야 쏠 수 있음
                        if (ny, nx) not in visited:
                            if maps[ny][nx]:
                                return True, ny, nx     # 쏠 수 있다면 반환
                            else:
                                dq.append((ny, nx, dist + 1))
                                visited.add((ny, nx))

        return False, -1, -1        # 쏠 수 있는 애가 없다면 False를 반환


def get_enemy(archers):
    enemy_set = set()
    cnt = 0

    for y in range(n - 1, -1, -1):      # 적이 내려오지말고, 궁수가 올라가면 됨
        enemy_set.clear()

        for x in archers:       # 궁수의 좌표
            flag, enemy_y, enemy_x = bfs(y, x)      # 적의 위치를 찾음

            if flag:
                enemy_set.add((enemy_y, enemy_x))       # 중복 처리, 같은 적을 쏠 수 있음

        cnt += len(enemy_set)

        for enemy_y, enemy_x in enemy_set:
            maps[enemy_y][enemy_x] = 0      # 적은 처리했음

    return cnt


if __name__ == "__main__":
    n, m, d = map(int, input().split())
    maps = [list(map(int, input().split())) for _ in range(n)]
    maps_original = [row[:] for row in maps]
    ans = 0

    for archers in combinations(range(m), 3):
        ans = max(ans, get_enemy(archers))
        maps = [row[:] for row in maps_original]        # 복구해야 됨

    print(ans)

---

3.  마무리