[이코테 Ch18-47] 청소년 상어 (구현)

👩🏻‍💻문제설명

[이코테 Ch18-47] 청소년 상어

✍️Idea Sketch

문제요약

그래프 공간

4×4크기의 공간이 있다.
한 칸에는 물고기가 한 마리 있다. 모든 물고기는 번호와 방향을 가지고 있다.
번호는 1~16의 자연수이며, 중복은 없다.
방향은 상하좌우, 대각선까지 포함하여 총 8가지이다. 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다. (반시계 방향)

이동 패턴

1. 상어가 물고기를 잡아먹는다. 맨 처음에, 상어는 (0, 0)에 있는 물고기를 먹는다.
2. 번호가 작은 물고기부터 이동한다.
3. 상어가 이동한다.

물고기의 이동

1. 번호가 작은 물고기부터 1칸만 이동한다.
2. 물고기가 있는 경우, 두 물고기의 위치를 교환한다.
3. 상어가 있는 칸이거나 벽인 경우, 방향을 반시계 방향으로 45도씩 틀고 이동 가능한지 확인한다.
4. 이동할 수 있는 칸이 없으면 이동하지 않는다.

상어의 이동

1. 상어의 방향은 최근에 잡아 먹은 물고기의 방향이다.
2. 상어가 바라보는 방향에 있는 물고기를 잡아 먹을 수 있다.
3. 종료 조건 : 잡아 먹을 수 있는 물고기가 없는 경우 종료한다.

목표 : 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

예시

초기 상태는 위와 같다. 상어가 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다.

이제 물고기가 이동한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 15번 물고기가 있다. 물고기가 있는 경우, 두 물고기의 위치를 교환한다.

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있다.
방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있으니 서로 위치를 바꾼다.

3번 물고기의 방향은 ↑이고, 벽이다. 45도 반시계 회전을 한 방향 ↖도 벽이니, 또 회전을 한다. ← 방향에는 상어가 있으니 또 회전한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환한다.

모든 물고기가 이동하면 위와 같다.
이제 상어가 이동한다. 상어의 방향은 ↘이고, 12번, 15번, 8번 물고기가 있는 칸으로 이동할 수 있다.
만약 8번 물고기가 있는 칸으로 이동하면, 아래 그림과 같다.

알고리즘 : 구현, 시뮬레이션, 완전 탐색 (DFS)

시뮬레이션과 완전 탐색을 함께 수행한다. 상어가 먹을 수 있는 물고기의 수가 여러 개인 경우가 존재하므로, 완전 탐색을 수행한다. 완전 탐색을 위해 DFS를 사용한다.

✍️소스코드

  import copy

  # 4 x 4 크기의 정사각형에 존재하는 각 물고기의 번호(없으면 -1)와 방향 값을 담는 테이블
  array = [[None] * 4 for _ in range(4)]

  for i in range(4):
      data = list(map(int, input().split()))
      # 매 줄마다 4마리의 물고기를 하나씩 확인하며
      for j in range(4):
          # 각 위치마다 [물고기 번호, 방향]을 저장
          array[i][j] = [data[j*2], data[j*2+1]-1]


  # 8가지 방향 정의
  dx = [-1, -1, 0, 1, 1, 1, 0, -1]
  dy = [0, -1, -1, -1, 0, 1, 1, 1]

  # 현재 위치에서 왼쪽으로 회전된 결과 반환
  def turn_left(direction):
      return (direction + 1) % 8

  result = 0 # 최종결과

  # 현재 배열에서 특정한 번호의 물고기 위치 찾기
  def find_fish(array, index):
      for i in range(4):
          for j in range(4):
              if array[i][j][0] == index:
                  return (i, j)
      return None

  # 모든 물고기를 회전 및 이동시키는 함수
  def move_all_fishes(array, now_x, now_y):
      # 1번부터 16번까지의 물고기를 차례대로 (낮은번호부터) 확인
      for i in range(1, 17):
          # 해당 물고기의 위치 찾기
          position = find_fish(array, i)
          if position != None:
              x, y = position[0], position[1]
              direction = array[x][y][1]
              # 해당 물고기의 방향을 왼쪽으로 계속 회전시키며 이동이 가능한지 확인
              for _ in range(8):
                  nx = x + dx[direction]
                  ny = y + dy[direction]
                  # 해당 방향으로 이동이 가능하다면 이동시키기
                  if 0 <= nx and nx < 4 and 0 <= ny and ny < 4:
                      if not (nx == now_x and ny == now_y):
                          array[x][y][1] = direction
                          array[x][y], array[nx][ny] = array[nx][ny], array[x][y]
                          break
                  direction = turn_left(direction)

  def get_possible_positions(array, now_x, now_y):
      positions = []
      direction = array[now_x][now_y][1]
      # 현재의 방향으로 계속 이동시키기
      for i in range(4):
          now_x += dx[direction]
          now_y += dy[direction]
          # 범위를 벗어나지 않는지 확인하며
          if 0 <= now_x and now_x < 4 and 0 <= now_y < 4 :
              # 물고기가 존재하는 경우
              if array[now_x][now_y][0] != -1:
                  positions.append((now_x, now_y))
      return positions

  # 모든 경우를 탐색하기 위한 DFS 함수
  def dfs(array, now_x, now_y, total):
      global result
      array = copy.deepcopy(array) # 리스트를 통째로 복사

      total += array[now_x][now_y][0] # 현재 위치의 물고기 먹기
      array[now_x][now_y][0] = -1 # 물고기를 먹었으므로 번호 값을 -1로 변환

      move_all_fishes(array, now_x, now_y) # 전체 물고기 이동시키기

      # 이제 다시 상어가 이동할 차례이므로, 이동 가능한 위치 찾기
      positions = get_possible_positions(array, now_x, now_y)
      # 이동할 수 있는 위치가 없다면 종료
      if len(positions) == 0:
          result = max(result, total) # 최댓값 저장
          return
      # 모든 이동할 수 있는 위치로 재귀적 수행
      for next_x, next_y in positions:
          dfs(array, next_x, next_y, total)


  # 청소년 상어의 시작 위치(0, 0)에서부터 재귀적으로 모든 경우 탐색
  dfs(array, 0, 0, 0)
  print(result)