청소년 상어(1)

백준 사이트의 19236번 문제

코딩 계획

Objective

• 모든 경우의 수를 고려하고 최댓값을 구해야해서 DFS로 해결
• 작은 수의 물고기를 차례대로 이동시키기 위해, 물고기 번호가 key 값이 되는 dict 변수에 데이터 저장
• 방향과 위치로 물고기를 찾아야하기 위해, grid에도 데이터 저장
• recursive하게 함수를 실행하므로 nested list와 dict 변수 deep copy
• 객체 지향적으로 구성할 방법이 직관적으로 생각나지 않아서 일단 rough하게 구현

Flow

1. 데이터 dict와 grid에 저장
2. 상어의 각 이동 선택이 노드가 되게 DFS 구현
   1. 상어가 이동하여 물고기를 먹음
   2. 물고기 번호대로 물고기 이동
   3. 상어가 이동할 수 있는 위치 탐색
   4. 상어가 각 이동을 선택하고 DFS하여 최댓값 반환
3. 최종 최댓값 출력

1. 데이터 dict와 grid에 저장

N = 4

fish = {}
grid = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    line = list(map(int, input().split()))
    for j in range(N):
        j0 = j*2
        j1 = j0 + 1
        fish_no = line[j0]
        fish_dir = line[j1]
        grid[i][j] = fish_no
        fish[fish_no] = [i, j, fish_dir]

2. 상어의 각 이동 선택이 노드가 되게 DFS 구현

DIRECTIONS = {
    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 dfs(i, j, fish, grid):
    ### 1. 상어가 이동하여 물고기를 먹음
    fish_no = grid[i][j]
    total = fish_no
    shark_dir = fish[fish_no][2]
    fish.pop(fish_no)
    grid[i][j] = 0
    
    ### 2. 물고기 번호대로 물고기 이동
    new_grid = [[a for a in line] for line in grid]
    new_fish = {k: v for k, v in fish.items()}
    for fish_no in sorted(new_fish.keys()):
        x, y, fish_dir = new_fish[fish_no]
        new_fish_dir = rotate(i, j, x, y, fish_dir)
        move(new_grid, x, y, new_fish_dir, new_fish)

    
    ### 3. 상어가 이동할 수 있는 위치 탐색
    ### 4. 상어가 각 이동을 선택하고 DFS하여 최댓값 반환
    l = [0]
    for i_, j_ in shark_destinations(i, j, shark_dir, new_grid):
        new_grid_ = [[a for a in line] for line in new_grid]
        new_fish_ = {k: v for k, v in new_fish.items()}
        l.append(dfs(i_, j_, new_fish_, new_grid_))
    
    return total + max(l)

코드 리뷰

• 굉장히 rough하게 구현함
• deep copy 고려해서 new_grid, new_fish로 구현했는데, 위치가 틀려서 new_grid_, new_fish_ 로 한번 더 함
• 맞긴 맞았음

리펙토링 계획

• ‘바다 생물’이라는 추상 클래스에서 ‘상어’, ‘물고기’ 상속시킬 생각
• deep copy 중복 제거

최종 코드

https://github.com/yehoon17/beakjoon/blob/main/python/19236.py

---

Next: 청소년 상어(2)