[백준] 17135 캐슬 디펜스

---

N*M의 격자판에서 3명의 궁수를 위치시켜 잡을 수 있는 적의 최대를 구하는 문제이다.

 

궁수가 적을 잡는 경우

1. 궁수는 D 거리 이하에 있는 적만을 잡을 수 있다.

2. 궁수는 가장 가까운 적을 죽인다.

3. 그러한 적이 여러명 존재할 경우 가장 왼쪽에 위치한 적을 죽인다.

4. 같은 적을 죽일 수 있다.

 

궁수 배치하기

가능한 모든 궁수들의 배치를 구해야 하기 때문에 itertools 모듈의 combinations를 사용한다.

 

죽일 적 찾기 & 적 죽이기

D 거리 이하에 위치하고 가장 가까운 적을 찾기 위해서 BFS를 활용한다. 이때 파이썬의 heapq 모듈을 사용한다.

궁수와 적간의 거리, 궁수의 위치를 큐에 저장한다. 단 거리가 D를 초과하면 잡을 수 있는 적이 존재하지 않기 때문에 (-1, -1)을 반환한다.

 

heapq 모듈은 원소의 순서에 따라 우선순위를 부여하기 때문에 (거리, Column, Row) 순으로 데이터를 삽입한다.

 

같은 적을 죽일 수 있기 때문에 각 궁수가 적을 찾자 마자 죽이는 것이 아니라 적을 모두 찾은 후 죽인다.

 

적 이동

적을 아래로 이동 시키기 위해 배열 전체를 라인 스왑 하는 것이 아니라 궁수의 위치를 한 칸 위로올린다.

 

 

Python

 

	from sys import stdin
	import heapq
	from itertools import combinations as cb
	readline = stdin.readline
	N, M, D = map(int, readline().split())
	dr = (0, -1, 0)
	dc = (-1, 0, 1)
	_map = [list(map(int, readline().split())) for _ in range(N)]
	all_archers = [[N-1, i] for i in range(M)]
	archers_cb = cb(all_archers, 3) # 궁수 자리 배치 모든 경우의 수
	def solve(archers_org):
	cnt = 0
	_map_cp = [[_map[i][j] for j in range(M)] for i in range(N)]
	archers = [[archers_org[i][0], archers_org[i][1]] for i in range(3)]
	for t in range(N):
	delete_rc = []
	# 죽일 적 찾기
	# BFS로 가장 가까운 적 찾는다.
	for archer in archers:
	r, c = bfs(_map_cp, archer[0], archer[1])
	if r != -1 and c != -1:
	delete_rc.append([r, c])
	# 적 죽이기
	for r, c in delete_rc:
	if _map_cp[r][c] != 0:
	_map_cp[r][c] = 0
	cnt += 1
	# 궁수의 위치 한 칸 위로
	for archer in archers:
	archer[0] -= 1
	return cnt
	def bfs(_map_cp, ar_r, ar_c):
	q = []
	heapq.heappush(q, [1, ar_c, ar_r]) # 가장 왼쪽의 적을 먼저 죽인다.
	# 최우선: 거리, 차선: 왼쪽으로 최소 힙에 정렬
	visited = [[False] * M for _ in range(D)]
	while q:
	d, c, r = heapq.heappop(q)
	visited[ar_r-r][c] = True
	if _map_cp[r][c] == 1 and d <= D:
	return r, c
	for i in range(3):
	nr, nc = r + dr[i], c + dc[i]
	if 0<=nr<N and 0<=nc<M and (abs(ar_r-nr) + abs(ar_c-nc)) <= D and ar_r-nr < D and not visited[ar_r-nr][nc]:
	heapq.heappush(q, [d+1, nc, nr])
	visited[ar_r-nr][nc] = True
	return -1, -1 # 죽일 수 있는 적이 없는 경우
	ans = 0
	for archers in archers_cb:
	ans = max(ans, solve(archers))
	print(ans)

view raw BOJ17135.py hosted with ❤ by GitHub