19236.청소년상어

Intro

• 곧 삼성 SW 역량 모의 테스트가 있어서 19236번 청소년상어 문제를 풀어보았습니다.

청소년상어

문제 설명

• 목표
  • 상어가 먹을 수 있는 물고기 번호의 합의 최댓값
• 상태
  • 4x4 공간
  • 각 칸에는 물고기가 있고, 물고기는 번호(1~16)와 방향(상하좌우, 대각선)을 가지고 있다.
  • 상어는 (0, 0)에서 시작하고, 방향은 해당 칸에 있는 물고기의 방향을 따른다.
• 물고기 이동
  • 상어가 이동한 뒤, 모든 물고기가 번호 순으로 이동한다. (번호가 작은 순부터 이동)
  • 물고기는 한 칸만 이동 가능
  • 상어가 이동할 수 있는 칸 1. 물고기가 있는 칸 2. 빈 칸
  • 상어가 이동할 수 없는 칸 1. 상어 존재 2. 공간 경계 넘는 칸
  • 이동할 수 있는 칸이 나올 때까지 반시계 방향 45도 회전(최대 7번)
  • 다른 물고기가 있는 칸으로 이동할 때는 서로 위치 교환 fish1, fish2 = fish2, fish1
• 상어 이동
  • 물고기 이동이 끝난 뒤, 현재 방향에 있는 모든 칸 중 물고기가 있는 칸으로 이동
  • 상어는 한 번에 여러 칸 이동 가능
  • 이동 중에는 물고기 먹지 않음
  • 이동한 칸의 물고기를 먹고 해당 물고기의 방향을 갖는다.
  • 이동할 수 있는 칸이 없으면 종료

문제 접근 방식

• 상어를 먼저 옮긴 후, 물고기 위치를 옮겨줍니다.
• 여기서, 먹을 수 있는 물고기 번호 합의 최대값을 알아야 하므로, array를 여러번 움직일 것을 고려해, deepcopy를 이용해 copy해둡니다.
• 또한, 방향을 쉽게 바꿀수 있도록 1번부터 8번까지 해당 방향의 좌표를 dictionary로 미리 만들어둡니다.

문제 답안

• from copy import deepcopy
    
  direction = {
      1: [-1, 0],
      2: [-1, -1],
      3: [0, -1],
      4: [1, -1],
      5: [1, 0],
      6: [1, 1],
      7: [0, 1],
      8: [-1, 1]
  }
    
  def move_shark(i, j, direct, eaten):
      global arr, ans, direction
      backup = deepcopy(arr)
      move_fish()
      if ans < sum(eaten):
          ans = sum(eaten)
      for k in range(1, 4):
          # 상어의 새로운 좌표 찾기
          ni = i + direction[direct][0] * k
          nj = j + direction[direct][1] * k
          # 물고기가 없다면 스킵하기
          if 0 <= ni < 4 and 0 <= nj < 4:
              if arr[ni][nj][0] == 0:
                  continue
              fish = arr[ni][nj][0]
              direct = arr[ni][nj][1]
              store = arr[i][j][1]
              arr[i][j][0] = 0
              arr[ni][nj][0] = -1
              move_shark(ni, nj, arr[ni][nj][1], eaten + [fish])
              # 물고기 원상태로 되돌려놓기 
              arr[i][j][0] = -1
              arr[ni][nj][0] = fish
              direct = store # ㅎ... 방향땜에 얼마나 헤맸나 ^0^
      # 맵 이전으로 돌려놓기
      arr = backup
    
        
    
  def move_fish():
      for k in range(1, 17):
          # 먼저 해당 fish의 location을 찾는다 
          flag = False
          if k in eaten:
              continue
          for i in range(4):
              for j in range(4):
                  if arr[i][j][0] == k:
                      fish_i = i
                      fish_j = j
                      fish_direction = arr[i][j][1]
                      flag = True
                      break
              if flag:
                  break
          else:
              continue
            
          # 물고기가 이동할 수 있는지 확인해본다.
          while True:
              ni = fish_i + direction[fish_direction][0] 
              nj = fish_j + direction[fish_direction][1]
              if 0 <= ni < 4 and 0 <= nj < 4 and arr[ni][nj][0] != -1:
                  temp_fish = arr[ni][nj]
                  arr[ni][nj] = arr[fish_i][fish_j] 
                  arr[fish_i][fish_j] = temp_fish
                  break
              else:
                  # 만약 이동할 수 없다면 이동 방향을 1 추가한다.
                  fish_direction +=1 
                  if fish_direction > 8:
                      fish_direction = fish_direction % 8
                  arr[fish_i][fish_j][1] = fish_direction
    
  arr = []
  # 처음에 배열 만들기
  for i in range(4):
      list1 = []
      temp = list(map(int, input().split()))
      for j in range(4):
          list1.append([temp[2*j], temp[2*j+1]])
      arr.append(list1)
    
  # 상어가 뭐 먹었는지 체크하기 
  eaten = []
  eaten.append( arr[0][0][0])
  ans = 0
    
  # 상어 위치 바꾸기 
  arr[0][0][0] = -1
  shark_i = 0
  shark_j = 0 
  shark_dir = arr[0][0][1]
    
  move_shark(shark_i, shark_j, shark_dir, eaten)
    
    
  print(ans)
    
  # 메모리: 29956 KB
  # 시간: 88ms