백준 17135번: 캐슬 디펜스 (파이썬, 완전탐색, 구현)

 정말 어려운 문제였다.

처음 문제를 봤을때 완전탐색 혹은 DP중에 고민했는데 시간복잡도가 M개 중에 3 개를 뽑는 조합 mC3 = m(m-1)(m-2)/6, 적들이 N번 움직이므로 반복문 O(N), 사정거리 D만큼, M열에 대해 거리를 탐색해야 하니

O(N^2)으로 M= 15, N = 15일 때 455*15*15*10= 10^6으로 시간제한인 1초에 넉넉하게 맞출 수 있어 완전탐색으로 풀어야 겠다고 생각할 수 있었다.

 

 그러나 구현 문제를 거의 처음 풀어봐서 시간이 오래 걸렸는데 반복문이 많이 중첩되다 보니 순서나 반복값에 있어서 헷갈림이 많았다. 

 

 알고리즘은 간단하다. 먼저 조합으로 [0:M]에 대해 3개를 뽑는다. 이때 궁수의 위치는 N행에 고정이므로 열의 크기에 대해서 조합을 뽑아야 한다.

그다음 적과 궁수의 거리를 측정하는 것을 N번 반복해야 하는데, N번 반복하면 모든 행이 각각 한번씩 내려감에 따라 남은 배열의 값은 모두 0이기 때문이다. 또한 거리 측정은 N-1행부터 N-1-D행까지 수행하였는데, 거리가 최소일 때는 두 점이 수직일 때, 즉 두 점이 같은 열에 있을 때이기 때문이다.

거리를 각각 측정한 후 각각의 배열에 대해서 거리, 열 순으로 정렬한다. 그 후 동시에 공격가능하더라도 적을 제거한 횟수는 한번만 늘려야 하기에 한번 공격한 곳은 배열값을 0으로 바꾸었다.

그리고 그래프를 한칸 내려주면 된다.

 

 삼성 코테는 외부 라이브러리 사용이 불가하다 하니 조합 구현법을 따로 익혀두긴 해야겠다.

 

import sys
from itertools import combinations
from copy import deepcopy


def length(x,y,x2,y2):
    return abs(x-x2)+abs(y-y2)


N, M, D = map(int, sys.stdin.readline().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

candidates = list(combinations(range(M), 3))  # 0~M-1열중에 3개에 배치 되므로 [0:M]개중에 3개를 뽑는다
max_ = 0

for candidate in candidates:  # 조합으로 궁수 세명 경우의 수
    cnt = 0
    graph_for = deepcopy(graph)

    for row in range(N):  # N번 반복
        pre = [[], [], []]
        for three in range(3):  # 궁수 세명
            for d in range(D):  # 사정 거리가 D인 경우, N-1행부터 N-1-D행까지 닿으니깐 (직선 거리)
                for col in range(M):
                    if 0 <= N-1-d < N and graph_for[N-1-d][col] == 1:
                        pre[three].append((length(N-1-d, col, N, candidate[three]), N-1-d, col))

        for sam in range(3):  # 한번에 하나만 지울 수 있음
            pre[sam].sort(key=(lambda x: (x[0], x[2])))  # 거리 최소, 거리가 같으면 제일 작은 인덱스
            if pre[sam]:  # 빈 배열이 있을 수도 있어서
                r, c = pre[sam][0][1], pre[sam][0][2]
                if pre[sam][0][0] <= D and graph_for[r][c] == 1:
                    # 36줄에서 배열 값을 0으로 하므로 이미 공격한 곳을 다시 공격X(동시 공격 가능하나, 카운트는 하나만 늘려야 하기에)
                    cnt += 1
                    graph_for[r][c] = 0

        # 그래프 한칸 내리기
        for move in range(-1, -N, -1):
            graph_for[move] = graph_for[move - 1]
        graph_for[0] = [0 for __ in range(M)]

    max_ = max(cnt, max_)

print(max_)