[백준] 19236번: 청소년 상어 - 파이썬(python)

 

 

나의 풀이

from collections import deque
import heapq
import copy

def move_fish(shark, fish) :
  for i in range(1,17) : # 1번~16번물고기까지 차례로 이동
    x,y = fish[i][0],fish[i][1]
    if x==-1 or y==-1 : # 없어진 물고기
      continue
    rotate = shark[x][y][1] # i번 물고기의 방향

    for _ in range(8) :
      nx = x + dx[rotate%8]
      ny = y + dy[rotate%8]
      # 해당 방향의 다음 칸이 범위안이고, 빈칸이거나 물고기가 존재한다면
      if 0<=nx<4 and 0<=ny<4 and shark[nx][ny][0] > -1 : 
        tmp = shark[nx][ny]
        shark[nx][ny] = [shark[x][y][0],rotate]
        shark[x][y] = tmp
        fish[shark[x][y][0]] = [x,y]
        fish[shark[nx][ny][0]] = [nx,ny]
        break
      else :
        rotate = (rotate+1)%8
    
shark_arr = [[] for _ in range(4)] # x,y 위치에 있는 물고기정보 [물고기번호,방향]
fish_arr = [[-1,-1] for _ in range(17)]  # x번 물고기의 위치 [x,y]
for i in range(4) :
  data = list(map(int, input().split()))
  for j in range(4) :
    shark_arr[i].append([data[j*2],data[j*2+1]-1])
    fish_arr[data[j*2]] = [i,j]

# 상어x, 상어y, 상어방향, 지금까지 먹은 물고기 합, 상어arr, 물고기arr
q = deque([[0,0,shark_arr[0][0][1],shark_arr[0][0][0],shark_arr,fish_arr]]) 

fish_arr[shark_arr[0][0][0]] = [-1,-1]
shark_arr[0][0] = [-1,-1] # 0,0에 상어가 있으므로 -1,-1 로 갱신 

# ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 
dx = [-1,-1,0,1,1,1,0,-1]
dy = [0,-1,-1,-1,0,1,1,1]

answer = []

while q :
  x,y,rotate,total,shark,fish = q.popleft()

  # 물고기 이동
  move_fish(shark,fish)
  
  cnt = 0
  nx = x
  ny = y
  # 상어 이동
  while True :
    nx += dx[rotate%8]
    ny += dy[rotate%8]
    
    # 해당 방향의 다음 칸이 범위를 벗어났다면
    if nx<0 or nx>=4 or ny<0 or ny>=4 :
      if cnt == 0 : # 더이상 이동할 수 없는 상어의 경우
        heapq.heappush(answer, -total)
      break
      
    if 0<=nx<4 and 0<=ny<4 and shark[nx][ny][0] > 0 : 
      nrotate = shark[nx][ny][1]
      ntotal = total + shark[nx][ny][0]
      nshark = copy.deepcopy(shark)
      nshark[x][y] = [0,0] # 기존의 상어가 있던자리는 빈칸
      nshark[nx][ny] = [-1,-1] # 다음으로 상어가 갈 자리는 -1
      nfish = copy.deepcopy(fish)
      nfish[shark[nx][ny][0]] = [-1,-1] # 없어진 물고기는 -1
      q.append([nx,ny,nrotate,ntotal,nshark,nfish])
      
print(-answer[0])

거의 3시간?은 걸린 문제 ㅋ.... 정답률 60% 실화냐고.. 이렇게 어려운데..? 풀고 보니 역시 골드2였다 ㅋㅋ

 

처음으로 제출한 풀이는 정답이지만, 코드가 난잡하고 가독성이 좋지 않다.

그도 그럴것이 3시간 동안 의식의 흐름대로 풀었기 때문이다..ㅋ

따라서 이코테 책에 있는 예시풀이를 참고하여 다시 깔끔하게 풀이를 작성하였다.

확실히 중요한 것은, 무작정 코드를 줄이기 위해 나도 헷갈리는 코드를 작성하는 것 보다

기능에 맞게 여러 함수를 만들고, 가독성이 좋게 작성하는 것이 호흡이 긴 문제를 풀 때 유리하다는 것이다.

 

 

좋은 풀이

import copy

def find_fish(index,arr) :
  for i in range(4) :
    for j in range(4) :
      if arr[i][j][0] == index :
        return (i,j)
  return None

def move_fish(now_x, now_y, arr) :
  for i in range(1,17) : # 1번~16번물고기까지 차례로 이동
    position = find_fish(i,arr)
    if position != None :
      x,y = position[0],position[1]
      direction = arr[x][y][1] # i번 물고기의 방향
      for _ in range(8) :
        nx = x + dx[direction%8]
        ny = y + dy[direction%8]
        # 해당 방향의 다음 칸이 범위안일때
        if 0<=nx<4 and 0<=ny<4 : 
          if not (nx == now_x and ny == now_y) :
            arr[x][y][1] = direction
            arr[x][y],arr[nx][ny] = arr[nx][ny],arr[x][y]
            break
        direction = (direction+1)%8

# 상어가 현재 위치에서 먹을 수 있는 모든 물고기의 위치 반환
def get_possible_positions(arr, now_x, now_y):
  positions = []
  direction = arr[now_x][now_y][1]
  for i in range(4) :
    now_x += dx[direction]
    now_y += dy[direction]
    if 0<=now_x<4 and 0<=now_y<4 :
      if arr[now_x][now_y][0] != -1 :
        positions.append((now_x,now_y))
  return positions
        
arr = [[None] * 4 for _ in range(4)] # x,y 위치에 있는 물고기정보 [물고기번호,방향]
for i in range(4) :
  data = list(map(int, input().split()))
  for j in range(4) :
    arr[i][j] = [data[j*2],data[j*2+1]-1]

# ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 
dx = [-1,-1,0,1,1,1,0,-1]
dy = [0,-1,-1,-1,0,1,1,1]

answer = 0
def dfs(now_x, now_y, total, arr):
  global answer
  array = copy.deepcopy(arr)
  print(now_x,now_y,total)
  total += array[now_x][now_y][0] # 현재 위치의 물고기 먹기
  array[now_x][now_y][0] = -1 # 현재 위치의 물고기를 먹었으므로 물고기번호를 -1로 변환
  
  # 물고기 이동
  move_fish(now_x, now_y, array)

  # 상어가 이동가능한 위치 찾기
  positions = get_possible_positions(array, now_x, now_y)
  if len(positions) == 0 : # 상어가 더 이상 이동할 수 있는 위치가 없는 경우
    answer = max(answer, total) # answer 값을 최댓값으로 저장
    return

  for next_x, next_y in positions :
    dfs(next_x,next_y,total,array) # for문안에서 작성했으므로 return 사용x . return 사용하면 1개만 실행하고, 다음 반복문 실행되기 전에 return 되므로 끝남
      
dfs(0,0,0,arr)
print(answer)