[BOJ] 17143번 낚시왕 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

https://www.acmicpc.net/problem/17143

풀이

문제를 이해하면서 문제를 크게 3가지 작은 문제로 쪼갰다.
1. 특정열에 존재하는 상어들 중 제일 위쪽에 있는 상어 제거하기
2. 상어 각각 이동시키기
3. 같은칸에 있는 상어면 큰 것만 남기기

이때 2.파트가 핵심이라고 느꼈고, 어떻게 구현할지 고민하면서 시간복잡도를 따져보니 상어를 각각 이동시킬때 한칸씩 이동하도록 코드를 짜면 총 10억으로 시간 초과가 날 것으로 보였다.

그래서 시간복잡도를 줄이기 위한 방법을 찾았고, 좌우를 똑같이 왕복하면 같은 상태가 되는 점을 이용해 나머지 연산을 통해 시간복잡도를 줄였다. 이때, 구체적인 예시를 적어서 방법을 찾았던게 좋은 방법이었던 것 같다.

1,3 파트의 경우 모두 정렬을 이용해서 풀었는데, 더 나은 풀이가 없을지 찾아봐야겠다.

추가로 관련된 정보를 Class로 모아서 관리하는게 코드를 짤 때 훨씬 직관적이어서 개인적으로 잘 맞는 것 같다. 그리고, 1,2,3,4와 같은 값을 코드 상단에서 UP, DOWN, LEFT, RIGHT로 정의해두고 코드에서 쓰는 것도 유용했다.

인덱스가 1부터 시작하는게 문제에서 주어지면 이 부분을 계속 고려하면서 코드를 작성하자. 한번 헷갈리면 다 꼬인다.

[시간 초과 관련]
Python3로 제출했을때 시간초과가 나서 sys.stdin.readline을 추가했고, 그래도 시간초과가 나서 PyPy3로 제출하니 통과되었다.

import sys
input = sys.stdin.readline

UP, DOWN, RIGHT, LEFT = 1, 2, 3, 4
DX_DY = [None, (-1, 0), (1, 0), (0, 1), (0, -1)]


def change_direction(dir):  # 방향 전환
    if dir == UP:
        return DOWN
    elif dir == DOWN:
        return UP
    elif dir == LEFT:
        return RIGHT
    elif dir == RIGHT:
        return LEFT
    else:
        print("error")


def is_valid(x, y):  # 격자 범위 안에 있는지
    if 0 <= x < R and 0 <= y < C:
        return True
    return False


class Shark:
    def __init__(self, r, c, s, d, z):
        self.x = r # 인덱스 0부터
        self.y = c # 인덱스 0부터
        self.speed = s
        self.direction = d  # 1(UP),2(DOWN),3(RIGHT),4(LEFT)
        self.size = z

    def move(self):  # 1초 후
        if self.direction in [LEFT, RIGHT]:
            self.speed %= ((C - 1) * 2)
        else:  # UP,DOWN
            self.speed %= ((R - 1) * 2)

        for _ in range(self.speed):  # 이만큼 이동 위에서 나머지해서 max 99
            dx, dy = DX_DY[self.direction]
            if is_valid(self.x + dx, self.y + dy):
                self.x, self.y = self.x + dx, self.y + dy
            else:
                # Direction 바꾸고 이동
                self.direction = change_direction(self.direction)
                dx, dy = DX_DY[self.direction]
                self.x, self.y = self.x + dx, self.y + dy


R, C, M = map(int, input().split())

sharks = []
for _ in range(M):
    r, c, s, d, z = map(int, input().split())
    r, c = r - 1, c - 1  # 인덱스 0기준으로
    sharks.append(Shark(r, c, s, d, z))

ans = 0
for remove_y_idx in range(C):  # 0~C-1
    # 1. 해당 열 중 가장 위에 있는 상어 제거
    sharks.sort(key=lambda shark: (shark.x))  # 처음발견된게 행이 가장 작도록
    for i, shark in enumerate(sharks):
        if shark.y == remove_y_idx:
            ans += shark.size
            sharks.pop(i)
            break

    # 2. 상어 이동
    for shark in sharks:
        shark.move()

    # 3. 같은 위치에 상어 여러개면 큰 것만 남기기
    new_sharks = []
    check_x_y = set()
    sharks.sort(key=lambda shark: -shark.size)  # 크기 큰게 무조건 먼저
    for shark in sharks:
        if (shark.x, shark.y) in check_x_y:
            continue  # 이미 있으면
        new_sharks.append(shark)
        check_x_y.add((shark.x, shark.y))
    sharks = new_sharks

print(ans)