백준 구현 대비 청소년 상어

문제:https://www.acmicpc.net/problem/19236
걸린시간 1시간30분

접근법

코딩테스트를 통해 느낀점을 바탕으로 알고리즘을 푸는 연습을 해야함
1, 설계 후 구현
구현하는 것은 설계가 다 끝난 뒤에 하는것, 디버깅은 틀린 로직을 찾는 것이 아니고 오타를 찾는 과정임을 명심하자. 설계와 구현 연습을 별도로 해야함
2, 도식화
각각의 단계들을 나눠 준 후 차근차근 구현
3, 모듈화

위 세가지를 유념해서 문제를 풀어야함

먼저 물고기들이 한사이클 움직인 후 상어가 움직임
이때 주의할점은 기존상태의 배열에서 물고기들이 한사이클 움직이고 나서 상어가 0,0으로 들어가는게 아니라

상어가0,0으로 들어간 후 (일단 한마리 먹었다 치고) 알고리즘의 시작임

물고기가 한사이클 움직이는 movefish 함수를 구현해줌

그후 상어가 움직이는 sharkmove함수를 구현해준다.

이떄 상어가 갈수 있는 경우의 수가 여러가지 이므로, dfs 방식으로 구현해주어야함

각각의 재귀 함수 실행 마다. deepcopy를 해줘서 분기 마다 다른 그래프를 넘겨주어야 한다 (중요)

전체코드

import copy
movelist=[[0,-1],[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1]]
answer=0
def movefish(graph):
  movei,movej=-1,-1
  for f in range(1,17):
    check=False
    for i in range(4):
      for j in range(4):
        if graph[i][j][0]==0 or graph[i][j][0]=='S':
          continue
        elif graph[i][j][0]==f:
          check=True
          movei,movej=i,j

    
    if check==True:
      count=0
      while count<8:
        ni,nj=movei+movelist[graph[movei][movej][1]-1][1],movej+movelist[graph[movei][movej][1]-1][0]
        if 0<=ni<4 and 0<=nj<4:
          if graph[ni][nj][0]=='S':
            graph[movei][movej][1]=(graph[movei][movej][1])%8+1
            count+=1
          else:
            graph[movei][movej],graph[ni][nj]=graph[ni][nj],graph[movei][movej]
            break
        else:
          graph[movei][movej][1]=(graph[movei][movej][1])%8+1
          count+=1


  return graph

def sharkmove(graph,curi,curj,total):
  global answer
  total=total+graph[curi][curj][0]
  answer=max(answer,total)
  graph[curi][curj]=['S',graph[curi][curj][1]]


  graph=movefish(graph)
  mi=movelist[graph[curi][curj][1]-1][1]
  mj=movelist[graph[curi][curj][1]-1][0]

  ni,nj=curi+movelist[graph[curi][curj][1]-1][1],curj+movelist[graph[curi][curj][1]-1][0]
  while 0<=ni<4 and 0<=nj<4:
    if graph[ni][nj][0]!=0:
      newgraph=copy.deepcopy(graph)
      newgraph[curi][curj]=[0,0]
      sharkmove(newgraph,ni,nj,total)
    ni+=mi
    nj+=mj
fishgraph=[[] for j in range(4)]
for i in range(4):
  d=list(map(int, input().split()))
  for j in range(4):
    fishgraph[i].append([d[j*2],d[j*2+1]])
sharkmove(fishgraph,0,0,0)
print(answer)