낚시왕(1)

백준 사이트의 17143 문제

코딩 계획

1. 입력값 저장
2. 제일 가까운 상어 포획 구현
3. 상어 이동 구현

구현

1. 입력값 저장

• 제일 가까운 상어을 O(n_cols)로 탐색할 수 있도록 grid에 상어 정보 저장
• 한 칸에 최대 한 마리의 상어가 들어갈 수 있게 하고, O(n_sharks)로 순회할 수 있도록 dict로 상어 기록

class Pool:
    def __init__(self, n_rows, n_cols):
        self.n_rows = n_rows
        self.n_cols = n_cols
        self.grid = [[0 for _ in range(n_cols)] for _ in range(n_rows)]
        self.shark_at = {}
        
    def add(self, i, j, shark):
        if self.grid[i][j] < shark.size:
            self.grid[i][j] = shark.size
            self.shark_at[(i, j)] = shark

class Shark:
    def __init__(self, speed, direction, size):
        self.speed = speed
        self.direction = direction
        self.size = size

n_rows, n_cols, n_sharks = map(int, input().split())
pool = Pool(n_rows, n_cols)
for _ in range(n_sharks):
    i, j, speed, direction, size = map(int, input().split())
    shark = Shark(speed, direction, size)
    pool.add(i-1, j-1, shark)

초기에 상어 위치를 저장할 때와 이동 후 가장 큰 상어의 위치를 저장할 때 동시에 사용할 수 있도록 Pool.add() 구현

2. 제일 가까운 상어 포획 구현

제일 가까운 상어를 탐색하고 grid 와 shark_at 업데이트

class Pool:
    ...

    def catch(self, j):
        for i in range(self.n_rows):
            if self.grid[i][j] > 0:
                caught_size = self.grid[i][j]
                self.grid[i][j] = 0
                self.shark_at.pop((i, j))
                return caught_size
        return 0

3. 상어 이동 구현

Pool.add() 활용

class Pool:
    ...
    
    def move_sharks(self):
        self.grid = [[0 for _ in range(n_cols)] for _ in range(n_rows)]
        shark_at_ = self.shark_at
        self.shark_at = {}
        for (i, j), shark in shark_at_.items():
            x, y = shark.move(i, j, self.n_rows, self.n_cols)
            self.add(x, y, shark)

class Shark:
    ...

    def move(self, i, j, n_rows, n_cols):
        #1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽
        if self.direction < 3:
            n = n_rows * 2 - 2
            dx = self.speed % n
            if self.direction == 1:
                x = i - dx
                if x < 0:
                    x = -x
                    self.direction = 2
                    if x > n_rows - 1:
                        x = n + 1 - x
                        self.direction = 1
            else:
                x = i + dx
                if x > n_rows - 1:
                    x = n - x
                    self.direction = 1
                    if x < 0:
                        x = -x
                        self.direction = 2                        
            return x, j
        else:
            n = n_cols * 2 - 2
            dy = self.speed % n
            if self.direction == 4:
                y = j - dy
                if y < 0:
                    y = -y
                    self.direction = 3
                    if y > n_cols - 1:
                        y = n + 1 - y
                        self.direction = 4
            else:
                y = j + dy
                if y > n_cols - 1:
                    y = n - y
                    self.direction = 4
                    if y < 0:
                        y = -y
                        self.direction = 3   
            return i, y

TODO: Shark.move() 리펙토링

정방향, 역방향 이동을 이어붙여서 circular하게 순회하도록 구현하려고 했는데 양끝점이 중복이 되어서 일단 위와 같이 구현함

결과

테스트 케이스는 전부 통과했지만, 제출하면 10% 때에 실패함

코드

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