[파이썬] 백준 17135: 캐슬디펜스 (골드3)

[파이썬] 백준 17135: 캐슬디펜스 (골드3)

17135번: 캐슬 디펜스

---

문제

---

풀이

 

1. 입력

from itertools import combinations as C
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w,D = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]
locs = list(C(range(w),3))

• 조합으로 궁수들 x좌표 만들어주기.

 

2. 시뮬레이션

answer = []
for loc in locs:
    kill = 0
    temp = [row[:] for row in arr]

    for _ in range(h):
        eliminate = set()

        for x in loc:
            targets = []

            for i in range(h-D,h):
                for j in range(x-D,x+D+1):
                    dist = abs(i-h)+abs(j-x)
                    if 0<=j<w and 0<=i<h and temp[i][j] and dist <= D:
                        targets.append((dist,j,i))

            if targets:
                targets.sort(key=lambda x:(x[0],x[1]))
                d,a,b = targets[0]
                eliminate.add((a,b))

        for a,b in eliminate:
            temp[b][a] = 0
            kill += 1

        temp.pop()
        temp.insert(0,[0]*w)

    answer.append(kill)
print(max(answer))

• locs의 각 원소들이 (x1,x2,x3)형태로 이루어져있다. 구해야 할 케이스 길이와 같다.
• for _ in range(h) : 최대 h번 반복된다. (적이 최대 h칸 전진 가능하다). 사실 맨 위에있는 적 좌표만 구하면 조금 더 효율적으로 풀 수 있다.
• stage마다 적을 제거한다. 제거할 적은 eliminate에 넣는다. 같은 적을 공격할 수 있으므로, 각 궁수별 죽일 적을 모두 고른 후 eliminate에 넣고 한 번에 제거한다.
• for i in range(h-D,h):  for j in range(x-D,x+D+1): 각 궁수별 자기 앞으로  h-D부터 h-1까지, 좌 우로는 +- D까지 탐색한다.
• 적의 좌표 (j,i)와 궁수 좌표 (x,h)의 거리 dist가 조건을 만족하면 죽일 적 리스트 targets에 넣는다.
• targets이 존재하면 거리, x좌표 순으로 정렬해주고 죽일 적을 eliminate에 넣는다.
• 적을 죽이고 temp.pop() 적을 전진시키고. 더미 0을 TEMP에 채워넣는다.

 

---

전체코드

from itertools import combinations as C
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w,D = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]
locs = list(C(range(w),3))

answer = []
for loc in locs:
    kill = 0
    temp = [row[:] for row in arr]

    for _ in range(h):
        eliminate = set()

        for x in loc:
            targets = []

            for i in range(h-D,h):
                for j in range(x-D,x+D+1):
                    dist = abs(i-h)+abs(j-x)
                    if 0<=j<w and 0<=i<h and temp[i][j] and dist <= D:
                        targets.append((dist,j,i))

            if targets:
                targets.sort(key=lambda x:(x[0],x[1]))
                d,a,b = targets[0]
                eliminate.add((a,b))

        for a,b in eliminate:
            temp[b][a] = 0
            kill += 1

        temp.pop()
        temp.insert(0,[0]*w)

    answer.append(kill)
print(max(answer))

 

코멘트

30퍼쯤에서 틀린다면 '같은 적을 공격할 수 있다' 이 조건을 놓친거고

70퍼쯤에서 틀린다면 사정거리가 맵 크기보다 클 수 있다는 점을 놓친거다.