[BOJ] 17135 캐슬 디펜스 - Python

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

17135번: 캐슬 디펜스

BFS  + 조합 + 우선순위 정렬 을 사요애야하는 조금 복잡한 문제다.

어느 적부터 쏴야 할지를 선택해야 하고..

궁수를 배치하는 건 조합을 사용하고

적이 어딨는지 탐색하는 부분은 BFS

 

 

 

from itertools import combinations
import heapq

# 위, 오른, 왼 방향
dx = [-1, 0, 0]
dy = [0, 1, -1]

#입력
N, M, D= map(int,input().split())
arra = [[0]*M for _ in range(N)]
for i in range(N):
    line = list(map(int,input().split()))
    for j in range(M):
        arra[i][j] = line[j]

bower = [i for i in range(M)]
arra.append(bower)


def bfs(line, bow, arr):
    global D
    res = [[] for _ in range(32)]
    visit = [[0]*M for _ in range(N+1)]
    q = []
    visit[line][bow] = True
    heapq.heappush(q, (0, bow, line))
    while q:
        front = heapq.heappop(q)
        dist = front[0]
        x = front[2]
        y = front[1]
        if arr[x][y] == 1:
            heapq.heappush(res[dist], (y,x))
        for i in range(3):
            xx = x + dx[i]
            yy = y + dy[i]
            if 0 <= xx <N and 0<= yy < M and visit[xx][yy] == False:
                heapq.heappush(q, (dist+1, yy, xx))
                visit[xx][yy] = True
    return res
maxval = 0
aaa = 0
tup = set()
for p in combinations(bower,3):
    bow_arr = [0]*M
    for i in p:
        bow_arr[i] = 2
    bow = []
    cnt = 0
    arra[N] = bow_arr
    for i in range(len(bow_arr)):
        if bow_arr[i] == 2:
            bow.append(i)
    one = bfs(N, bow[0], arra)
    two = bfs(N, bow[1], arra)
    three = bfs(N, bow[2], arra)
    tar = set()
    lines =set()
    for j in range(1, N+1):
        tempset = set()
        visit = [0]*3
        for i in range(j, j+D):
            if len(one[i]) > 0 and visit[0] == False:
                while True:
                    if not one[i]:
                        break
                    o = heapq.heappop(one[i])
                    if o[1] in lines:
                        continue
                    if o not in tar:
                        tempset.add(o)
                        visit[0] = True
                        break
            if len(two[i]) > 0 and visit[1] == False:
                while True:
                    if not two[i]:
                        break
                    o = heapq.heappop(two[i])
                    if o[1] in lines:
                        continue
                    if o not in tar:
                        tempset.add(o)
                        visit[1] = True
                        break
            if len(three[i]) > 0 and visit[2] == False:
                while True:
                    if not three[i]:
                        break
                    o = heapq.heappop(three[i])

                    if o[1] in lines:
                        continue
                    if o not in tar :
                        visit[2] = True
                        tempset.add(o)
                        break
        lines.add(N-j)
        for temp in tempset:
            tar.add(temp)
    cnt = len(tar)
    if maxval < cnt:
        maxval = cnt

print(maxval)