청소년 상어(2)

백준 사이트의 19236번 문제

구현하는 데에 집중하느라 코드가 깔끔하지 못 했다. 청소년 상어
그래서 객체 지향적으로 리펙토링하면서 개선하는 작업에 들어갔다.

리펙토링

로깅

알고리즘은 이미 구현했기 때문에 틀릴 리가 없는데 자꾸 이상한 결괏값이 나왔다.
그래서 디버깅하고자 로깅 함수를 만들어서 틀린 부분을 찾아 고쳤다.
원인은 self를 몇몇 군데에 누락해서 그런 것이었다.

DEBUG = False

def log(x, indent=0):
    if DEBUG:
        lines = x.__str__().split('\n')
        for line in lines:
            print('  '*indent, line, sep='')

로그

dfs start ------------------------------
location: (0, 0)
shark ate: number: 7, location: (0, 0), direction: ↘
[' 0    ', ' 2,  ←', '15, ↘', ' 9, ↗']
[' 3,  ↑', ' 1, ↗', '14,  →', '10,  ↑']
[' 6,  ↑', '13, ↘', ' 4,  ←', '11, ↙']
['16,  ↑', ' 8,  →', ' 5, ↖', '12, ↖']

rotate and move fish
[' 0    ', ' 2, ↙', ' 9,  ←', '10,  ↑']
[' 6,  ↑', '12, ↖', ' 1, ↗', '14,  →']
['16,  ↑', ' 5, ↖', '15, ↘', '13,  ↑']
[' 3, ↙', ' 4,  ←', '11, ↙', ' 8,  →']

shark_destinations: [(1, 1), (2, 2), (3, 3)]
dfs start ------------------------------
location: (1, 1)
shark ate: number: 19, location: (1, 1), direction: ↖
[' 0    ', ' 2, ↙', ' 9,  ←', '10,  ↑']
[' 6,  ↑', ' 0    ', ' 1, ↗', '14,  →']
['16,  ↑', ' 5, ↖', '15, ↘', '13,  ↑']
[' 3, ↙', ' 4,  ←', '11, ↙', ' 8,  →']

...

shark_destinations: []
sharks: [15]
dfs end ================================
sharks: [7, 25, 33, 15]
dfs end ================================
##############################
33

Direction 클래스

정수로 입력 받은 방향 정보를 벡터로 활용하기 위해 구현

class Direction:
    vectors = {
        1: (-1, 0),
        2: (-1, -1),
        3: (0, -1),
        4: (1, -1),
        5: (1, 0),
        6: (1, 1),
        7: (0, 1),
        8: (-1, 1)
    }
    arrows = {
        1: " ↑",
        2: "↖",
        3: " ←",
        4: "↙",
        5: " ↓",
        6: "↘",
        7: " →",
        8: "↗",
    }

    
    def __init__(self, direction_id):
        self.direction_id = direction_id

    @property
    def vector(self):
        return self.vectors[self.direction_id]
        
    @property
    def arrow(self):
        return self.arrows[self.direction_id]

    def rotate(self):
        self.direction_id += 1
        if self.direction_id > 8:
            self.direction_id = 1

        return self.direction_id

    def __str__(self):
        return self.arrow

MarineLife, Shark, Fish 클래스

처음에는 MarineLife 클래스를 추상 클래스로 구현하고 move() 메소드를 추상 메소드로 하려고 했다. 코딩하다 보니 그럴 필요 없어서 그냥 구현했는데 추상 클래스는 유지했다.

from abc import ABC, abstractmethod

class MarineLife(ABC):
    def __init__(self, number=0):
        self.number = number
    
    def move(self, new_location):
        self.location = new_location

    @property
    def destination(self):
        i, j = self.location
        dx, dy = self.direction.vector
        return (i + dx, j + dy)

class Shark(MarineLife):
    def eat(self, fish):
        self.move(fish.location)
        self.number += fish.number
        self.direction = fish.direction    
        
    def __str__(self):
        return f'number: {self.number}, location: {self.location}, direction: {self.direction}'

class Fish(MarineLife):
    def __init__(self, i, j, number, direction):
        super().__init__(number)
        self.location = (i, j)
        self.direction = direction

    def rotate(self):
        self.direction_id = self.direction.rotate()

    def __str__(self):
        return f'number: {self.number}, location: {self.location}, direction: {self.direction}'

Sea 클래스

대부분의 알고리즘이 포함된 클래스

class Sea:
    def __init__(self, size, shark):
        self.size = size
        self.grid = [[0 for _ in range(size)] for _ in range(size)]
        self.fish_dict = {}
        self.shark = shark

    def add(self, fish):
        i, j = fish.location
        self.grid[i][j] = fish.number
        self.fish_dict[fish.number] = fish

    def is_destination_valid(self, marin_life):
        i, j = marin_life.destination
        return -1 < i < self.size and -1 < j < self.size

    def is_shark(self, fish):
        return self.shark.location == fish.destination
        
    @property
    def fish_list(self):
        return sorted(self.fish_dict.keys())

    def shark_eat(self, location):
        i, j = location
        eaten_fish_number = self.grid[i][j]
        eaten_fish = self.fish_dict[eaten_fish_number]
        self.shark.eat(eaten_fish)
        self.fish_dict.pop(eaten_fish_number)
        self.grid[i][j] = 0

    def rotate_fish(self, fish_number):
        # log(f'rotating {fish_number} fish', 2)
        while True:
            fish = self.fish_dict[fish_number]
            # log(f'direction: {fish.direction}', 3)
            if self.is_destination_valid(fish):
                if not self.is_shark(fish):
                    break

            fish.rotate()
        # log(self, 2)

    def swap(self, location1, location2):
        i1, j1 = location1
        i2, j2 = location2
        self.grid[i1][j1], self.grid[i2][j2] = self.grid[i2][j2], self.grid[i1][j1]

    def fish_at(self, location):
        i, j = location
        return self.grid[i][j]
        
    def move_fish(self, fish_number):
        fish = self.fish_dict[fish_number]
        destination_fish_number = self.fish_at(fish.destination)
        
        self.swap(fish.location, fish.destination)

        location = fish.location
        fish.move(fish.destination)
        if destination_fish_number > 0:
            self.fish_dict[destination_fish_number].move(location)

    def is_fish(self, location):
        i, j = location 
        return self.grid[i][j] > 0
    
    def shark_destinations(self):
        destinations = []
        while self.is_destination_valid(self.shark):
            self.shark.move(self.shark.destination)
            if self.is_fish(self.shark.location):
                destinations.append(self.shark.location)
        return destinations
    
    def get_shark_number(self):
        return self.shark.number

    def __str__(self):
        grid_ = []
        for line in self.grid:
            line_ = []
            for fish_number in line:
                if fish_number > 0:
                    s = f'{fish_number:>2}, {self.fish_dict[fish_number].direction}'
                else:
                    s = f'{fish_number:>2}    '
                line_.append(s)
            grid_.append(line_)

        grid_.append('')
        return '\n'.join([str(line) for line in grid_])

DFS 함수

def dfs(location, sea):
    log('dfs start ------------------------------')
    log(f'location: {location}')

    sea.shark_eat(location)
    log(f'shark ate: {sea.shark}')
    log(sea)

    log('rotate and move fish')
    for fish_number in sea.fish_list:
        sea.rotate_fish(fish_number)
        sea.move_fish(fish_number)
    log(sea)

    sea_list = [sea]
    shark_destinations = sea.shark_destinations()
    log(f'shark_destinations: {shark_destinations}')
    for shark_destination in shark_destinations:
        new_sea = copy.deepcopy(sea)
        sea_list.append(dfs(shark_destination, new_sea))

    log(f'sharks: {[s.shark.number for s in sea_list]}')
    max_shark_number_sea = max(sea_list, key=lambda x: x.shark.number)
    log('dfs end ================================')
    return max_shark_number_sea

후기

self를 누락해서 골치 좀 아팠지만 그 덕분에 깔끔한 로깅을 구현할 수 있었다.
아쉬운 점은 벡터 계산하고 grid에 참조할 때 계속 언패킹, 패킹하는 작업을 더 세련되게 구현 못한 것이다.
그리고 Sea 클래스의 메소드 순서가 깔끔하지 않은 것도 조금 아쉽긴 하다.
하지만 대체적으로 깔끔하고 만족스럽게 코딩했다.

최종 코드

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