BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/17135
내가 작성한 코드
import sys
from collections import deque, defaultdict
from itertools import combinations
dir = [(0, -1), (-1, 0), (0, 1)]
def get_data():
read = sys.stdin.readline
N, M, D = map(int, read().rstrip().split())
enermies = []
for r in range(N):
crnt = list(map(int, read().rstrip().split()))
for c in range(M):
if crnt[c] == 1:
enermies.append((r,c))
available = [(N, c) for c in range(M)]
return N, M, D, enermies, available
def distance(x, y):
return abs(x[0] - y[0]) + abs(x[1] - y[1])
def attack(towers, enermies, N, M, D):
died = []
for tower in towers:
q = deque([(tower, 0)])
visitied = defaultdict(bool)
visitied[tower] = True
while q:
crnt, cost = q.popleft()
if crnt in enermies:
died.append(crnt)
break
for d in dir:
nw_crnt = tuple(sum(x) for x in zip(crnt, d))
if 0 <= nw_crnt[0] < N and 0 <= nw_crnt[1] < M and cost + 1 <= D and not visitied[nw_crnt]:
visitied[nw_crnt] = True
q.append((nw_crnt, cost+1))
return set(died)
def move(enermies, N):
nw_enermies = []
for r, c in enermies:
if r+1 < N:
nw_enermies.append((r+1, c))
return nw_enermies
N, M, D, enermies, available = get_data()
mx_died = 0
for towers in combinations(available, 3):
crnt_enermies = enermies[:]
total_died = 0
while crnt_enermies:
crnt_died = attack(towers, crnt_enermies, N, M, D)
total_died += len(crnt_died)
for dead in crnt_died:
crnt_enermies.remove(dead)
crnt_enermies = move(crnt_enermies, N)
mx_died = max(mx_died, total_died)
print(mx_died)
- 조합 (combinations)
- 궁수를 배치할 수 있는 모든 경우의 수
- 공격 (attack)
- 적이 모두 사라질 때까지
- 궁수의 위치에서 BFS로 가장 가까운 적 찾기
- 집합(set)으로 중복을 고려하여 적 제거
- 이동 (move)
- 성에 도착하는 것을 고려
- 아래로 한 칸 이동
다른 사람이 작성한 코드
import sys
from itertools import combinations
from heapq import heappop, heappush
n, m, d = map(int, sys.stdin.readline().rstrip().split())
MAP = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
arr = []
castle_pos = [i for i in range(m)]
archer_cases = tuple(combinations(castle_pos, 3))
answer = 0
def get_enemy_count():
global arr
cnt = 0
for i in range(n):
for j in range(m):
if arr[i][j] == 1: cnt += 1
return cnt
def attack_enemy(archer_case_index):
global arr
remove_list = []
attacked = [[False for _ in range(m)] for _ in range(n)]
cnt = 0
for archer_pos in archer_cases[archer_case_index]:
pq = [] # [거리, x, y]를 우선순위 큐에 삽입
for i in range(n-1, -1, -1):
for j in range(m):
if arr[i][j] == 1:
diff = abs(n-i) + abs(archer_pos-j)
if diff <= d:
heappush(pq, [diff, j, i])
if pq:
_, x, y = heappop(pq)
remove_list.append([y, x])
for y, x in remove_list:
if not attacked[y][x]:
attacked[y][x] = True
cnt += 1
arr[y][x] = 0
return cnt
def move_enemy():
global arr
arr[-1] = [0 for _ in range(m)]
for i in range(-1, -n, -1):
arr[i] = arr[i-1]
arr[0] = [0 for _ in range(m)]
def simulation(archer_case_index):
cnt = 0
while get_enemy_count() != 0:
cnt += attack_enemy(archer_case_index)
move_enemy()
return cnt
for i in range(len(archer_cases)):
arr = [[MAP[i][j] for j in range(m)] for i in range(n)]
cnt = simulation(i)
if answer < cnt: answer = cnt
print(answer)
- 우선순위 큐를 이용한 BFS
- (거리, x, y)로 거리와 가장 왼쪽의 적을 선택하는 방식
[백준 17135] 캐슬 디펜스(Python)
4개월 동안 방치한 문제를 이제야 풀었다.N\*M 격자판 어딘가에 적이 있고, N+1행, 모든 칸에 성이 있다. 캐슬 디펜스는 궁수 3명을 성에 배치 할 때, 주어진 공격 범위안의 가장 가까운 적 1명을 퇴
velog.io
기억해야할 것
- 문제 파악
- 처음에 성의 위치가 어디인지 작성되지 않아서 해매었음
- 모든 격자에 성을 배치하는 방식으로 작성했었음
'코딩테스트' 카테고리의 다른 글
[백준][구현] 낚시왕 (0) | 2022.02.17 |
---|---|
[백준][기하학] 이사 (0) | 2022.02.15 |
[백준][그리디] 단어 수학 (0) | 2022.02.10 |
[백준][BFS] MooTube (Silver) (0) | 2022.02.08 |
[백준][구현] 치킨 배달 (0) | 2022.02.08 |