백준 17135 캐슬 디펜스
https://www.acmicpc.net/problem/17135
난이도 : 골드 5
유형 : 구현
문제
주어진 배열 아래에 궁수 3명을 배치해 사정거리 내의 가장 가까운 왼쪽 적을 제거한다.
매 턴 마다 적군들은 아래로 한 칸 씩 이동한다.
최대로 제거할 수 있는 적의 수를 구하는 문제.
풀이
생각해야할 것들
1. 주어진 배열의 가장 아래에 행을 만든다고 생각하고 궁수를 3명 배치함 (M개의 칸에서 3칸 선택)
2. 사정거리 D 안에서 가장 가까운 왼쪽 적을 공격 (단, 모든 궁수가 동시에 공격 = 여러 궁수가 같은 적을 공격하는 경우 있음)
3. 공격 턴이 끝나면 적이 아래로 한 칸 이동
1번은 파이썬의 내장 함수 combination을 이용해서 M개 중 3개를 선택했다.
함수를 하나 만들어서 파라미터로 궁수의 y좌표 위치를 넘겨주었다.
일단 3번에서 언급한 매 턴마다 적군들이 아래로 이동하는 부분을 그냥 for문을 돌리면서 마지막 행부터 하나씩 올라가는 식으로 해결했다.
궁수들이 한 번에 공격해야하기 때문에 배열을 하나 만들어서 이번 턴에 죽는 적군을 저장했다.
2번을 해결하기 위해 각 궁수별로 bfs를 돌리면서 거리 1부터 D까지 좌, 상, 우 순서대로 방향을 검사했다. 적군이 있다면 배열에 저장하고 break.
정답 코드
import sys
input = sys.stdin.readline
from collections import deque
from itertools import combinations
N, M, D = map(int, input().split())
matrix = []
for _ in range(N):
line = list(map(int, input().split()))
matrix.append(line)
dx = [0, -1, 0]
dy = [-1, 0, 1]
def kill(archor):
temp_matrix = [x[:] for x in matrix]
killed = [[0] * M for _ in range(N)]
result = 0
#적군 움직이는 턴 (한칸씩 내려가는거를 for문을 반대로 돌리는 거로 생각)
for i in range(N-1, -1, -1):
#이번턴 죽는 애(궁수들이 한번에 공격하니까)
this_turn = []
#각 궁수별로 bfs 돌리면서 사정거리 안 제일 가까운 적군 찾기
for ay in archor:
#첫 값은 궁수 바로 위 칸으로 넣어줌
dq = deque([(i, ay, 1)])
while dq:
x, y, d = dq.popleft()
if temp_matrix[x][y] == 1:
this_turn.append((x, y))
if killed[x][y] == 0:
killed[x][y] = 1
result += 1
break
if d < D:
for di in range(3):
nx = x + dx[di]
ny = y + dy[di]
if 0 <= nx < N and 0 <= ny < M:
dq.append((nx, ny, d+1))
#한 턴에 공격한 애들 한번에 죽이기
for x, y in this_turn:
temp_matrix[x][y] = 0
return result
answer = 0
archor_pos = list(combinations([i for i in range(M)], 3))
for a in archor_pos:
answer = max(answer, kill(a))
print(answer)굉장히 삼성스러운 구현 문제였다.
이 풀이에서는 궁수의 위치를 지정하기 위해 itertools의 combination을 사용하였지만 삼성 코테에서는 itertools 사용이 불가하기 때문에 조합을 구현해서 푸는 식으로도 연습해봐야할 것 같다.
