백준(Baekjoon) 17143번 : 낚시왕 - python 풀이

JISU LIM·2024년 3월 25일

Algorithm Study Records

목록 보기

78/79

🔴 문제 개요

문제 원문 - 백준 온라인 저지(Baekjoon Online Judge)

🚀 난이도 : GOLD 1

본 문제는 BOJ의 삼성 SW 역량 테스트 기출 문제 문제집에 수록된 문제입니다.

위 그림처럼, 낚시왕은 오른쪽으로 한 칸씩 이동하며 상어를 잡습니다. 이때 1초마다, 아래 적힌 순서대로 일이 일어납니다.

낚시왕이 오른쪽으로 한 칸 이동한다.
낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
상어가 이동한다.

상어는 주어진 속도(칸/초)와 방향으로 이동하고, 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동합니다. 또한 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있습니다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹습니다.

이때, 낚시왕이 잡은 상어 크기의 합을 구하는 문제입니다.

⊖ 제한사항

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)
둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

🟠 Solution

문제에서 주어진 조건대로, 절차대로 구현하면 무난하게 구현할 수 있는 문제처럼 보입니다. 다만 문제 조건에서 파생하는 디테일한 세부 조건에 대해서 단번에 고려하기가 무척 어려웠던 문제였습니다. 우선 백본 코드부터 보겠습니다.

🦴 Backborn

import sys
from typing import List, Optional

# input = sys.stdin.readline
input = lambda: sys.stdin.readline().rstrip()

def kill_shark(...):
	"""
    상어 잡기 연산
    """
	pass
    
def move_shark(...):
	"""
    상어 이동 연산
    """
	pass

R, C, M = map(int, input().rstrip().split())
matrix = [[None for _ in range(C)] for _ in range(R)]

dy = [-1, 1, 0, 0] # <detail 1> 순서대로 상, 하, 우, 좌 임에 유의
dx = [0, 0, 1, -1]

for _ in range(M):
    r, c, s, d, z = map(int, input().rstrip().split())
    matrix[r-1][c-1] = [s, d-1, z]	# 인덱스가 0부터 시작함을 고려

answer = 0

for c in range(C):
    answer += kill_shark(matrix, c)
    move_shark(matrix)

print(answer)

격자의 크기와 상어의 수를 입력으로 받고, 격자(matrix)를 정의해주었습니다. 이때 격자에서 상어의 정보를 List[int] 형으로 관리할 것이며, 상어가 없는 경우 None으로 표시할 것입니다.

🚨 문제 디테일 1 : 문제에서 1~4 까지 방향 정보를 매핑해서 제공합니다. 이때 저는 주로 방향 정보를 상, 하, 좌, 우 순으로 관리해 활용하는데, 문제에서는 1: 상, 2: 하, 3: 우, 4: 좌 임에 유의해야 합니다.

이후 M마리 상어 정보를 받아 matrix에 저장하고, 각 칸마다 상어를 잡고(kill_shark()), 상어를 이동시키는(move_shark()) 연산을 수행해주면 됩니다. 각 메서드를 구현해보겠습니다.

1️⃣ kill_shark()

해당 열(c)에 대해서 모든 행(r)을 탐색하며, 처음 만나는 상어를 잡고, 해당 상어의 크기를 반환해주기만 하면 되는 간단한 메서드입니다.

🚨 문제 디테일 2 : 상어를 잡으면, 격자판에서 잡은 상어가 사라집니다.

def kill_shark(matrix: List[List[Optional[List[int]]]], c: int) -> int:
    """
    :param matrix : 격자
    :param c : 현재 열
    
    c열에서 모든 행(r)을 탐색해 처음 만나는 상어의 크기를 반환한다.
    반환 전 상어 정보를 삭제한다.
    """

    for r in range(R):
        if matrix[r][c]:
            result = matrix[r][c][2]	# 상어 크기 정보
            matrix[r][c] = None 		# <detail 2> 상어 정보 삭제
            return result

    return 0	# 상어가 없으면 0 반환

2️⃣ move_shark()

상어를 잡은 이후엔 상어가 움직이는 연산을 수행해야 합니다. 해당 메서드에서 주의해야할 디테일이 많습니다.

우선, 격자 내 모든 칸을 탐색하며, 상어가 있는 곳을 찾습니다. 상어를 찾았다면 해당 좌표의 상어 정보(속력, 방향)을 고려해 해당 상어를 이동시킵니다. 이 과정까지의 문제 디테일은 아래와 같습니다.

🚨 문제 디테일 3 : 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있고, 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹습니다.

이를 위해서 바로 원본 격자에 이동 후 상어 정보를 삽입하면 안됩니다. 모든 상어는 동시에 움직이므로, 모든 상어의 이동 후에 동일 칸의 상어들에 대해 비교를 통해 가장 큰 상어만을 원본 격자에 반영해주어야 합니다. 이를 위해 보조 격자(tmp)를 활용해 이동 후 특정 칸의 가장 큰 상어 정보를 관리해주었습니다.

🚨 문제 디테일 4 : 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동합니다.
🚨 문제 디테일 5 : 상어는 입력으로 주어진 속도(칸/초)로 이동합니다.

이를 위해서 주어진 속력 만큼 반복문으로 상어를 모두 이동시켜볼 수 있습니다. 그러나, 상어는 최대 10,000마리 주어질 수 있고, 속력은 1,000까지 주어질 수 있습니다. 이 경우 상어를 이동시키는 연산 자체만 10,000,000 회이기 때문에, 최대 100칸의 col을 탐색하며 각 천 만회 이상의 연산을 해야 하니, TLE가 발생할 수밖에 없습니다.

이때, 격자의 크기는 R, C로 100까지인데 속력은 1,000까지 주어짐에 대해서 눈여겨봐야 합니다. 100칸을 1초에 1000번 움직인다면, 반복이 발생할 수 밖에 없습니다. 이 반복을 캐치해서 반복되는 연산을 줄여야 합니다.

크기가 1x3인 격자에서 오른쪽으로 이동시키는 경우를 보겠습니다. 같은 주기가 속력 4마다 반복됩니다.
크기가 1x4인 격자에서는 같은 주기가 속력 6마다 반복됩니다.
크기가 1x5인 격자에서는 같은 주기가 속력 8마다 반복됩니다. (그림 생략)

따라서 같은 주기가 $2(C-1)$ 마다 반복됨을 확인할 수 있습니다. 위 아래로 움직이는 경우에는 $2(R-1)$ 마다 반복되겠죠. 이를 통해 상어의 속력에 나머지 연산을 적용해서 반복을 없앨 수 있습니다.

이동이 끝난 상어 정보는 보조격자(tmp)의 해당 좌표에서 크기 비교 후 관리되고 있습니다. 모든 이동이 끝났다면, tmp의 정보를 원본격자(matrix)로 옮겨주어 1회 이동을 마무리합니다.

def move_shark(matrix: List[List[Optional[List[int]]]]) -> None:
    """
    :param matrix : 격자

    격자 내 모든 상어를 1초동안 움직인다.
    """
    tmp = [[None for _ in range(C)] for _ in range(R)]  # <detail 3> 이동 후 상어 좌표를 임시 저장할 보조 격자

    for r in range(R):
        for c in range(C):
            if not matrix[r][c]:
                continue

            s, d, z = matrix[r][c]
            matrix[r][c] = None     # 기존 상어 자리 비우기
            # 상어 좌표 이동
            ny, nx = r, c

            # <detail 5> 나머지 연산을 통해 반복 제거
            iteration = s
            # 상하 이동의 경우
            if d in (0, 1):
                iteration %= 2*(R-1)
            # 좌우 이동의 경우
            else:
                iteration %= 2*(C-1)

            # 상어 이동
            for _ in range(iteration):
                # <detail 4> 격자판의 경계를 넘는 경우 방향을 반대로
                if ny == 0 and d == 0:
                    d = 1
                if ny == R-1 and d == 1:
                    d = 0
                if nx == 0 and d == 3:
                    d = 2
                if nx == C-1 and d == 2:
                    d = 3

                ny += dy[d]
                nx += dx[d]
            
            # <detail 3> 동일 격자 내에는 가장 큰 상어만 남도록
            if not tmp[ny][nx] or tmp[ny][nx] and tmp[ny][nx][2] < z:
                tmp[ny][nx] = [s, d, z]

    # <detail 3> 이동 후 상어 정보를 원본 격자에 반영
    for r in range(R):
        for c in range(C):
            matrix[r][c] = tmp[r][c]

📚 고찰

간단해 보이는 문제였지만 5가지 디테일을 정교하게 반영해야 풀이가 가능했던 문제였습니다. 이를 증명하듯, 난이도도 GOLD 1 수준의 구현 문제임을 확인할 수 있었습니다.

역시 중요한 건 문제의 조건을 잘 보는 것이었습니다. 방향의 정보가 상, 하, 우, 좌 로 주어지는 것이나, 상어가 격자 크기가 100인데 1000번 이동할 수 있는 것이나 모두 조건을 자세히 보지 않으면 고려하기 힘든 조건들입니다.

시간이 들어도, 코드 작성에 들어가기 전 문제의 모든 디테일을 파악하고 docstring으로 정리하는 습관을 들여야겠습니다.

✏️ TIL

lambda 식을 통해 자주 쓰는 sys 모듈의 인풋 + 개행 문자 제거(rstrip) 표현을 한 번에 작성할 수 있습니다.
- input = lambda: sys.stdin.readline().rstrip()
python type hint 작성 시, JAVA와 동일하게 Optional을 통해 None일수도 아닐 수도 있는 형을 표현할 수 있습니다.
- 이 경우, def foo(a: Optional[int]): -> None 와 같이 사용합니다.