17135번 문제
BFS+시뮬레이션 문제이다.
문제를 간략히 정리해보겠다.
- 적을 잡는 턴방식의 게임이다.
- 궁수는 성이 있는 칸에 3명을 배치한다.(여기서 성의 위치는 격자판 바로아래 행(n+1)이다.)
- 각각의 턴마다 세명의 궁수는 동시에 적을 죽인다.(두명의 궁수가 한명의 적을 죽이는 경우도 있다.)
- 죽은 적은 제외된다.
- 턴이 끝나면 적이 한칸 아래로 이동한다.(적이 성이 있는 칸으로 이동시 제외된다.)
- 적이 모든 격자판에서 제외시 게임은 종료된다.
- 궁수가 적을 죽이는 규칙
- 궁수가 공격하는 거리가 D이하인 적중 가장 가까운 적을 죽인다.
- 가장 가까운 적이 여럿일 때, 가장 왼쪽의 적을 공격한다.이때 궁수의 공격으로 제거할 수 있는 적의 최대 수를 구한다.
문제를 처음 접했을 때, 궁수를 어디에 위치해야 할까에 대해 고민했다.
궁수의 위치에 대한 규칙을 찾으면서 코드를 작성하던 중 생각났던 것은 조합이었다.
참고로 삼성 코테에서는 조합을 itertools로 import 하지 못한다고 한다. 따라서 이번 문제는 조합을 구현했다.
조합을 이용해서 문제를 해결할 시나리오를 아래에 적어봤다.
시나리오
- 궁수가 있을 수 있는 위치를 조합을 구현해서 경우의 수를 for 문 돌린다.
- 한 궁수가 죽일 수 있는 적의 (거리, y좌표, x좌표)를 bfs 탐색의 결과로 받아온다.(반환전에 정렬을 해줘서 문제의 조건인 "가장 가까운 적", "가장 왼쪽의 적"을 만족시켜 놓는다.)
- 그러면 한명의 궁수가 죽이는 적의 좌표 하나만 남게 된다.
- 이 좌표를 별도의 리스트(position)에 넣고, 3명의 궁수가 죽이는 적 좌표를 position에 넣는다.
- set처리를 해줘서 중복을 제거하고, 나온 좌표수 만큼 죽인 적으로 처리한다.
- 죽인 적의 자리는 빈칸으로 바꿔주고, 그래프를 한칸씩 내린다.
- 이 과정을 반복한다.
말로 설명하는 것 보다, 코드로 보는것이 좀 더 이해하기 쉬울 것이다.
코드
import sys
input=sys.stdin.readline
import copy
from collections import deque
# d거리 안에 가장 가까운 적을 찾는다.
def bfs(x,y,length):
q=deque()
q.append([x,y,length])
visited=[[0 for _ in range(m)] for _ in range(n+1)] #궁수의 위치까지 포함한 방문처리 리스트
visited[x][y]=1
attack=[] # 공격 가능한 적의 (거리, y좌표, x좌표)를 담을 리스트
while q:
x,y,length=q.popleft()
# 그래프의 해당 위치에 적이 있고, 공격가능 거리안에 있을 때
if temp[x][y]==1 and length<=d:
attack.append([length, y, x]) #정렬 조건에 따라 attack리스트에 추가
continue
for i in range(3):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<m:
# 다음 장소가 방문하지 않았고, 공격 가능 거리안에 있을 떄
if visited[nx][ny]==0 and length<=d:
q.append([nx,ny,length+1])
visited[nx][ny]=1
# 정렬해서 반환
return sorted(attack)
# 적이 아래로 한칸 씩 이동
def graph_move():
#n번째 행은 궁수 행이므로 n-1행부터 1번 행까지
for i in range(n-1, 0, -1):
for j in range(m):
temp[i][j]=temp[i-1][j]
# 맨 윗줄에 빈칸 추가
for i in range(m):
temp[0][i]=0
# 적의 존재 여부( while 문을 종료하기 위한 조건)
def is_empty():
for i in range(n):
for j in range(m):
if temp[i][j]==1:
return False
return True
# 조합 구현(yield 활용)
def combinations(array, r):
for i in range(len(array)):
if r==1:
yield [array[i]]
else:
for next in combinations(array[i+1:], r-1):
yield [array[i]]+next
n,m,d=map(int, input().split())
graph=[]
for _ in range(n):
graph.append(list(map(int, input().split())))
append_graph=[-1 for _ in range(m)]
graph.insert(n,append_graph) #마지막 줄에 궁수들 위치를 잡을 수 있도록 한줄 추가
#아래는 볼 필요 없다.(궁수 입장에서 탐색하기 때문에)
dx=[-1,0,0]
dy=[0,-1,1]
# 조합을 구할 리스트
items=[i for i in range(m)]
result=0
for a in combinations(items, 3):
temp = copy.deepcopy(graph) # 기존 그래프는 불변해야하므로, 깊은 복사
count=0 #죽인 적 수
while not is_empty():
position=[] #적 좌표 넣을 리스트
for i in range(3):
target_enemy=bfs(n,a[i],0)
if len(target_enemy)!=0:
target_enemy=target_enemy[0] # 가장 첫번째 인자를 뽑아옴(가장 가깝고, 왼쪽의 적)
position.append((target_enemy[2],target_enemy[1]))
#중복 제거
position=list(set(position))
for i in position:
temp[i[0]][i[1]]=0
count+=1
graph_move()
result=max(result,count)
print(result)코드를 보면 알겠지만, 최적화까지는 안된 문제라고 생각한다. 그렇지만, BFS와 조합을 구현해서 푸는 풀이법으로는 이게 맞다고 생각한다.
그리고 이번에 풀면서 처음으로 조합을 코드로 구현해보았는데, 다음엔 조합과 순열등을 정리해야겠다..
이번 문제는 역시 삼성 기출문제라 그런지, 구현에 꽤나 진심이다(?)
Backend Developer