[Python] 백준 19236번 - 청소년 상어

 

DFS, BFS, 백트래킹 등의 문제에서 경우의 수를 탐색할 때 입력 board 의 값들에 영향을 주는 경우 ( 특정 조건에서 어떤 원소 값을 바꾼다 등 ),  이전 상태의 list 로 돌아와야하는 경우가 있기 때문에 그냥 list 값을 넘겨주는 것이 아니라 deecopy 를 통해 값을 모두 복사해 넘겨줘야 함

 

import copy

def move_fish(sx, sy, fish, dir):
  go = [[], [-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]
  fish_pos = {}

  for i in range(4):
    for j in range(4):
      # 물고기인지 확인 
      # 물고기가 살아있어야됨 
      if fish[i][j] > 0 and (i, j) != (sx, sy):
        fish_pos[fish[i][j]] = (i, j)

  # 물고기는 번호가 작은 물고기부터 이동해야함
  for num in range(1, 17):
    if num in fish_pos:
      x, y = fish_pos.get(num)[0], fish_pos.get(num)[1]
      f_dir = dir[x][y]

      order = [o for o in range(f_dir, 9)]
      if len(order) < 8:
        for o in range(1, f_dir):
          order.append(o)

      # 시계방향으로 돌아간다 
      for o in order:
        dir[x][y] = o
        dx, dy = go[o][0], go[o][1]
        nx, ny = x + dx, y + dy

        # nx, ny 범위 체크 
        if 0 <= nx < 4 and 0 <= ny < 4:
          # 상어 없는지 체크 
          if (nx, ny) != (sx, sy):
            # 빈칸이라면
            if fish[nx][ny] == 0:
              fish_pos[fish[x][y]] = (nx, ny)
              fish[nx][ny] = fish[x][y]
              dir[nx][ny] = dir[x][y]
              fish[x][y] = 0
              break
            # 물고기 있다면 
            else:
              fish_pos[fish[x][y]] = (nx, ny)
              fish_pos[fish[nx][ny]] = (x, y)

              t_fish = fish[nx][ny]
              fish[nx][ny] = fish[x][y]
              fish[x][y] = t_fish
              
              t_dir = dir[nx][ny]
              dir[nx][ny] = dir[x][y]
              dir[x][y] = t_dir
              break
            # 상어가 있다면 반시계 회전


def dfs(x, y, eat, fish, dir):
  fish = copy.deepcopy(fish)
  dir = copy.deepcopy(dir)
  
  # 도착했으니까 물고기 먹음
  eat += fish[x][y]
  s_dir = dir[x][y]
  fish[x][y] = 0

  # 먹었으니까 물고기가 이동함
  # x, y 는 상어의 현재 위치 
  move_fish(x, y, fish, dir)

  # 물고기가 있는 칸이라면 상어가 이동
  # 상어가 이동 가능한 칸의 후보 
  dx = go[s_dir][0]
  dy = go[s_dir][1]

  global ans
  ans = max(ans, eat)

  for _ in range(1, 4):
    x, y = x + dx, y + dy
    if 0 <= x < 4 and 0 <= y < 4:
      # 물고기 있는 칸인지 확인
      if fish[x][y] != 0: 
        dfs(x, y, eat, fish, dir)


if __name__ == '__main__':
  go = [[], [-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]
  fish_data = []
  dir_data = []
  ans = 0

  for _ in range(4):
    tmp = list(map(int, input().split()))
    fish_tmp = [f for i, f in enumerate(tmp) if i%2==0]
    dir_tmp = [d for i, d in enumerate(tmp) if i%2==1]
    fish_data.append(fish_tmp)
    dir_data.append(dir_tmp)

  dfs(0, 0, 0, fish_data, dir_data)
  print(ans)