문제 링크
https://www.acmicpc.net/problem/19237
🕒 Python 풀이시간: 1시간 20분
N,M,K=map(int,input().split())
dx=[0,-1,1,0,0]
dy=[0,0,0,-1,1]
smellBoard=[[[0]*2 for _ in range(N)] for _ in range(N)]
board=[]
sharkInfo=dict()
for i in range(N):
arr=list(map(int,input().split()))
for j in range(N):
if arr[j]>0:
sharkInfo[arr[j]]=dict()
sharkInfo[arr[j]]["pos"]=[i,j]
board.append(arr)
nowDir=list(map(int,input().split()))
for i in range(1,M+1):
sharkInfo[i]["dir"]=nowDir[i-1]
for i in range(1,M+1):
sharkInfo[i]["dirPrior"]=dict()
for j in range(1,5):
sharkInfo[i]["dirPrior"][j]=list(map(int,input().split()))
def spreadSmell(smellBoard,sharkInfo):
for key in sharkInfo.keys():
x,y=sharkInfo[key]["pos"]
smellBoard[x][y][0]=key
smellBoard[x][y][1]=K
def moveShark(smellBoard,sharkInfo,board):
newBoard=[[0]*N for _ in range(N)]
deleteList=[]
for key in sharkInfo.keys():
x,y=sharkInfo[key]["pos"]
dir=sharkInfo[key]["dir"]
dirPrior=sharkInfo[key]["dirPrior"]
possibleBlock=[]
for i in range(4):
nx=x+dx[dirPrior[dir][i]]
ny=y+dy[dirPrior[dir][i]]
if nx<0 or ny<0 or nx>=N or ny>=N:
continue
if smellBoard[nx][ny][0]==0:
possibleBlock.append((0,i,dirPrior[dir][i],[nx,ny]))
elif smellBoard[nx][ny][0]==key:
possibleBlock.append((1,i,dirPrior[dir][i],[nx,ny]))
next=sorted(possibleBlock)[0]
sharkInfo[key]["pos"]=next[3]
sharkInfo[key]["dir"]=next[2]
nx,ny=next[3]
if newBoard[nx][ny]==0:
newBoard[nx][ny]=key
elif newBoard[nx][ny]>key:
deleteList.append(newBoard[nx][ny])
newBoard[nx][ny]=key
elif newBoard[nx][ny]<key:
deleteList.append(key)
for key in deleteList:
del sharkInfo[key]
return newBoard
def minusSmell(smellBoard):
for i in range(N):
for j in range(N):
if smellBoard[i][j][0]!=0:
if smellBoard[i][j][1]>1:
smellBoard[i][j][1]-=1
elif smellBoard[i][j][1]==1:
smellBoard[i][j]=[0,0]
t=0
while t<=1000:
spreadSmell(smellBoard,sharkInfo)
board=moveShark(smellBoard,sharkInfo,board)
minusSmell(smellBoard)
t+=1
if len(sharkInfo)==1:
break
if t==1001:
print(-1)
else:
print(t)어른 상어의 냄새 시뮬레이션: 생존을 위한 전략! 🦈💨
어른 상어가 움직이고 방향을 정하며 냄새를 남기는 상황을 시뮬레이션하는 문제이다. 문제를 몇단계로 나눠서 생각하는 것이 시뮬레이션 문제의 경우 간단하기 때문에 큰 단계로 나누었다. 첫번째, 상어가 현재 위치에서 냄새를 뿌린다. 움직이고 나서 원래 냄새를 뿌리지만 움직일 때, 다른 상어가 있는 칸에 갈 수 없기도 하고 후에 냄새가 1초에 따라 줄어들 때, 지난 상황이 반영되는 형태로 남아 있기 때문에 먼저 냄새부터 뿌려준다. 두번째는 상어가 주위의 방향에 따라 움직이고 마지막으로 냄새가 -1씩 줄어들거나 사라진다.
먼저 단계를 수행하기에 앞서서 입력받은 것들을 나타내야 하는데 이는 크게 냄새를 따로 다루는 배열과 상어의 현재 위치를 간단히 나타내는 배열 그리고 상어의 모든 정보를 담은 배열로 나누어 관리할 수 있다. 이처럼 관리하는 이유는 smellBoard 같은 경우 후에 냄새를 업데이트하기 위함을 생각해서 냄새 배열을 두어 관리하고 이에 바로 뿌릴 수 있게 하기 위함이며 상어의 종류와 남은 시간 초를 관리하기 위해 내부에 길이가 2인 배열로 둔다. 상어의 정보는 위치와 방향만 만지면 되기 때문에 번호에 따라 dict()으로 두었으며 방향의 우선순위에 대한 정보를 여기다가 같이 담아두었다. 마지막으로 위치를 따로 빼서 번호로 board를 둔 이유는 상어가 겹쳐졌을 때, 동시성을 보장하며 사라지는 것을 처리하기 위해서이다.
먼저 첫번째 단계를 수행하여 모든 상어의 정보를 번호로 dict()에서 찾으며 냄새 배열에 뿌려준다. 두번째 단계의 경우가 까다로운데 방향의 우선순위와 주위의 방향이 냄새가 있는지 없는지의 유무를 따져줘야하기 때문이다. 이 때, 우선순위에 따른 정렬을 사용할 수 있다. 먼저 모든 방향을 탐색하되 방향과 함께 해당 방향의 우선순위를 담는다. 또한 빈칸으로 가는건지 아니면 기존에 자신의 냄새가 나는데로 가는건지 또한 상태를 담는다. 이렇게 모든 정보들을 담고 정렬을 하면 가장 앞에 우리가 원하는 방향이 나오기 때문에 이를 가지고 이동을 시켜주면 된다. 최종 이동을 확정지을 시에는 board를 확인하여 현재 방향에 상어가 있는지 없는지를 확인해주면서 이를 모아두었다가 지워주면 된다. 마지막으로 냄새 배열을 순회하면서 냄새가 있는 칸에 한하여 냄새를 없애주거나 줄여주면 된다.
이렇게 Python으로 백준의 "어른 상어" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
