[백준] 19236 청소년 상어 Python
아기 상어에서 발전된 문제이다. 먼저, 물고기가 순서와 방향성이 매겨져 있고, 물고기가 순서대로 움직이고 상어가 움직이는 것이다. 이 문제에서 왜 DFS가 쓰였을까 생각을 하면, 물고기가 움직인 후 상어가 움직일 때 상어가 먹을 수 있는 물고기 번호의 합이 최댓값이 되어야한다. 문제에서 최댓값과 최솟값을 구하는 문제이면 DFS,BFS를 고려하자! 즉, 완전 탐색이기에 DFS를 사용했다. 코드를 짤 때, BFS가 편한데 아무래도 한 방향으로 쭉 가다보니 BFS 보다는 DFS를 쓰는게 나은 것 같다.
따라서, 한 방향에 여러 방향(북,동,남,서)를 탐색하는 경우 BFS를 쓰고, 한 방향으로 쭉 뻗어나가고 백트래킹을 써야할 경우는 DFS를 쓰는게 나은 것 같다.
다시, 백트래킹 개념을 소개하자면 경우의 수를 고려하여 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식으로, 조건에 맞지 않으면 중단하여 이전으로 돌아가 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘이다.
알고리즘 구조
-
graph 입력을 받는데, 물고기의 번호와 방향이 같이 입력된다. 따라서, graph[i][j]=[물고기 번호,방향]을 저장해야한다. 주의해야 하는 점은 방향 번호가 1번 부터 시작하기 때문에 -1을 하여 입력을 받아준다.
-
먼저 물고기가 움직이게 된다. 따라서, 1부터 16까지 for문을 돌려 grpah을 탐색하여 해당하는 번호의 물고기를 찾고, 물고기의 x,y 좌표를 업데이트 해준다. 만약 물고기의 x,y 좌표가 -1로 업데이트 되지 않았으면 그 물고기는 이미 상어에게 잡아먹혔으므로 continue를 해줘야한다.
-
물고기는 자리를 바꿀 물고기를 찾아야한다. 이때, 반시계방향으로 탐색을 하는데 찾았을 경우 바꿔준다.그 중 조건은 상어가 없어야한다! 주의해야하는 점은 바꾸기 전에 물고기 방향 좌표를 해당 좌표로 바꿔줘야한다. 왜냐하면 기존 방향에 상어가 있을 경우 반시계 방향으로 이동했을 것이고, 업데이트를 해줘야 해당 방향으로 이동할 수 있기 때문이다.
-
물고기가 다 이동했다면, 상어가 이동해야할 차례이다. 먼저, 상어의 방향을기록해주고, for문을 돌아(3번) i를 곱해줘야한다. 해당 방향으로 이동하기 때문이다. 그리고, 백트래킹을 위해 dfs로 넘겨줄 때, 기존의 graph가 잘 유지되도록 copy.deepcopy(graph)을 해줘야한다.
import sys
import copy
sys.setrecursionlimit(10**5)
sys.stdin=open("input.txt")
graph=[[]for _ in range(4)]
for i in range(4):
tmp=list(map(int,input().split()))
for j in range(0,8,2):
graph[i].append([tmp[j],tmp[j+1]-1])
#↑, ↖, ←, ↙, ↓, ↘, →, ↗
dx=[-1,-1,0,1,1,1,0,-1]
dy=[0,-1,-1,-1,0,1,1,1]
max_score=0
def dfs(sx,sy,score,graph):
global max_score
score+=graph[sx][sy][0] #상어 물고기 먹음
max_score=max(score,max_score)
graph[sx][sy][0]=0 #물고기 사라짐
#물고기 움직임
for f in range(1,17):
fx=-1
fy=-1
for i in range(4):
for j in range(4):
if graph[i][j][0]==f: #물고기 찾음
fx=i
fy=j
break
if fx==-1 and fy==-1: #해당하는 물고기 없음
continue
fd=graph[fx][fy][1] #물고기 방향
#물고기 이동
for i in range(8):
nd=(fd+i)%8
nx=fx+dx[nd]
ny=fy+dy[nd]
if 0<=nx<4 and 0<=ny<4 and not (nx==sx and ny==sy): #바꿀 물고기가 있다
graph[fx][fy][1]=nd #바꾸기 전에 바꾸는 방향을 업데이트 해줘야함
#한번에 할당
graph[fx][fy],graph[nx][ny]=graph[nx][ny],graph[fx][fy]
break
#상어 이동
sd=graph[sx][sy][1] #상어 이동 방향
for i in range(1,4): #반복 3번밖에 못한다
nx=sx+dx[sd]*i
ny=sy+dy[sd]*i
if 0<=nx<4 and 0<=ny<4 and graph[nx][ny][0]!=0: #물고기 있다
dfs(nx,ny,score,copy.deepcopy(graph))
dfs(0,0,0,graph)
print(max_score)