문제 링크
https://www.acmicpc.net/problem/19236
🕒 Python 풀이시간: 60분
import copy
fishes=dict()
board=[[0]*4 for _ in range(4)]
for i in range(4):
arr=list(map(int,input().split()))
for j in range(0,2*4,2):
a,b=arr[j],arr[j+1]
board[i][j//2]=a
fishes[a]=[i,j//2,b-1]
dx=[-1,-1,0,1,1,1,0,-1]
dy=[0,-1,-1,-1,0,1,1,1]
shark=[0,0,0]
score=board[0][0]
shark[2]=fishes[board[0][0]][2]
del fishes[board[0][0]]
board[0][0]=-1
answer=0
def moveFish(fishes,board,shark):
for fishNum in sorted(fishes.keys()):
x,y,d=fishes[fishNum]
for i in range(8):
nx=x+dx[(d+i)%8]
ny=y+dy[(d+i)%8]
if nx<0 or ny<0 or nx>=4 or ny>=4:
continue
if shark[0]==nx and shark[1]==ny:
continue
if board[nx][ny]!=-1:
fishes[board[nx][ny]][0]=x
fishes[board[nx][ny]][1]=y
fishes[fishNum]=[nx,ny,(d+i)%8]
board[nx][ny],board[x][y]=board[x][y],board[nx][ny]
break
def dfs(score,shark,newBoard,newFishes):
global answer
moveFish(newFishes,newBoard,shark)
t=1
while True:
nx=shark[0]+dx[shark[2]]*t
ny=shark[1]+dy[shark[2]]*t
if nx<0 or ny<0 or nx>=4 or ny>=4:
answer=max(answer,score)
return
if newBoard[nx][ny]==-1:
t+=1
continue
board=copy.deepcopy(newBoard)
fishes=copy.deepcopy(newFishes)
tmpNum=board[nx][ny]
tmpFish=fishes[tmpNum]
board[nx][ny]=-1
del fishes[tmpNum]
dfs(score+tmpNum,[nx,ny,tmpFish[2]],board,fishes)
t+=1
dfs(score,shark,board,fishes)
print(answer)청소년 상어의 모험: 물고기를 잡아라! 🦈✨
청소년 상어와 물고기들의 이동을 시뮬레이션 하는 문제이다. 먼저 상어가 (0,0)칸에 있는 물고기를 먹고 방향을 갖는 것을 처음 세팅으로 한 다음, 상어의 이동이 백트래킹과 같기 때문에, 즉 경우의 수로 깊이 들어갈 수 있기 때문에 이를 사용한다.
DFS 함수는 물고기의 이동을 한 후, 상어의 이동 가능한 모든 지점에서 DFS를 실행해준다. 이 때, 영역을 벗어났을 경우, 즉 상어가 더 이상 이동 불가능한 경우에 처한다면 정답을 갱신해 주면 된다. 물고기를 먹고 그 자리로 이동한 상황을 DFS로 넘겨주면 된다.
물고기 이동관련 함수는 물고기들의 위치를 가져오는 것부터 시작한다. 키 값을 통해 번호로 저장해둔 물고기들의 정보를 가져와서 순차적으로 이동을 해주면 된다. 이동이 불가능하다면 방향을 계속해서 틀어가면서 찾아준다. 이동이 가능한 경우에도 물고기가 이동하려는 칸에 있는 경우와 비어 있는 칸인 경우를 나누어서 바꿔주거나 그대로 이동하거나 해야한다.
이렇게 Python으로 백준의 "청소년 상어" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
