문제설명

->링크<-
특정 조건에 따라서 상어와 물고기가 움진인다 이 때 상어가 먹을 수 있는 물고기의 번호의 합의 최댓값을 출력해야 한다!!

해결방법

먼저 상어는 각 상황마다 어떤 물고기를 고를지 선택해야한다. 그 때 어떤 것을 선택하는지를 몰라서 완전탐색으로도 시간안에 충분히 해결 할 수 있을 것 같아보여서 완전탐색으로 시작을 햇다.

간단히만 보자면

1. DFS에서 번호의 합을 매개변수로 가지고
2. 더이상 상어가 이동할 수 없을때 그때의 합 sum을
3. result값과 비교해서 결괏값을 구해낸다

여기서
물고기의 이동과 상어의 이동 구현은 코드에서 이해하기 편하다.
간단히 설명하면

1. 방향벡터를 8가지 방향으로 만든다
2. 문제조건에 맞춰서 이동시켜 준다.

해답 코드

import sys
import copy
input = sys.stdin.readline

matrix = [[(0,0)] * 4 for _ in range(4)]
for j in range(4):
  tmp_list = list(map(int, input().split()))
  for i in range(4):
    matrix[j][i] = tmp_list[i*2], tmp_list[i*2+1]

direction = [(0,0), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1)]
#완전 탐색함수
result = -1
def DFS(sum, shark, matrix):
  global result
  matrix = copy.deepcopy(move_fish(matrix))
  candi = get_candi(shark, matrix)
  
  #종료조건 상어가 더이상 이동할 수 없을 때
  if not candi:
    result = max(sum, result)
    return
  for spot in candi:
    newY, newX = spot
    tmp = matrix[newY][newX]
    new_shark = [(newY,newX), tmp[1]]
    #이동할 위치와 전위치 처리해주기
    tmp_matrix = copy.deepcopy(matrix)
    #상어만 이동시키기
    matrix[newY][newX] = (-1,-1)
    matrix[shark[0][0]][shark[0][1]] = (0,0)
    #탐색시작
    DFS(sum+tmp[0], new_shark, matrix)
    #처리해줬던거 원상복귀
    matrix = copy.deepcopy(tmp_matrix)
    
def get_candi(shark, matrix):
  res = []
  d = shark[1]
  newY, newX = shark[0]
  for i in range(3):
    newY += direction[d][0]
    newX += direction[d][1]
    if newY >= 0 and newY < 4 and newX >= 0 and newX < 4:
      if matrix[newY][newX] != (0,0):
        res.append((newY,newX))
  return res
  
def move_fish(matrix):
  #1번 물고기부터 차례대로 이동
  for i in range(1, 17):
    fish = find_fish(matrix, i)
    #해당 물고기 없다면 패스
    if fish == None:
      continue
    Y, X = fish[0]
    d = fish[1][1]
    #i번 물고기를 8방향 중에서 이동하기
    for k in range(8):
      newY = Y+direction[d][0]
      newX = X+direction[d][1]
      #현재 방향에서 이동할 수 있으면 이동 후 반복문 종료
      if newY >= 0 and newY < 4 and newX >= 0 and newX < 4:
        if matrix[newY][newX] != (-1,-1):
          #새로운 위치가 비어있는 경우
          if matrix[newY][newX] == (0,0):
            matrix[newY][newX] = (i,d)
            matrix[Y][X] = (0,0)
            break
          #새로운 위차가 물고기가 있는 경우
          else:
            tmp = matrix[newY][newX]
            matrix[newY][newX] = (i,d)
            matrix[Y][X] = tmp
            break
      #회전시켜주기
      d+=1
      if d > 8:
        d = 1
  #모든 물고기에 대해서 이동이 끝났다면
  return matrix
def find_fish(matrix, num):
  for i in range(4):
    for j in range(4):
      if matrix[i][j][0] == num:
        return [(i,j), (num, matrix[i][j][1])]
  return None
  
  return matrix
#move_fish()를 작동했을 때 matrix값이 잘 바뀌는지 확인


#메인문
start_sum = matrix[0][0][0]
start_shark = [(0,0),matrix[0][0][1]]
matrix[0][0] = (-1,-1)
DFS(start_sum, start_shark, matrix)
print(result)

걸린 시간

첫째날에 2시간 30분동안 풀었지만 풀리지 않았고
둘째날에 드디어 풀었다

두 시간을 합치면 총 4시간 반이 걸린 문제였다.

너무 시간이 오래걸렸다
이문제는 삼성전자 코테문제이며 1번문제를 1시간 정도에 풀었으니
합격을 위해서라면 위시간보다 2시간이나 단축해야한다.
개인적으로 시간을 줄이려면 디테일을 확인했어야 했다.

처음 코드가 돌아갔을때는 1시간정도 걸렸지만 코드를 정독하면서
어디에서 논리오류가 발생햇는지를 발견하는데 오래 걸렸다!!!

예를들면 이런 논리 오류가 있었다.
1. 16번 물고기까지 이동을 진행해야 하는데
range(1,16)로 코드를 짰다 하....

2. DFS함수가 하나 끝나면 matrix를 전상황이랑 아예 똑같이 해줬어야되는데 상어의 위치만 다시 원위치해놔서 틀렸다.

3. 깊은복사 deepcopy를 생각못하고 얕은 복사로 진행했다.