백준 낚시왕 [17143] 파이썬(Python) 코드 + 해설

백준 17143 낚시왕 문제

문제 설명

낚시왕은 크기가 R×C인 격자판에서 상어 낚시를 한다. 격자판의 각 칸에는 상어가 있을 수 있으며, 상어는 위치 (r,c), 속력 s, 이동 방향 d, 크기 z를 가진다.

낚시왕은 첫 번째 열의 왼쪽에 위치하며, 매 초마다 오른쪽으로 한 칸씩 이동한다. 매 시간마다 다음과 같은 일이 발생한다:

1. 낚시왕이 이동한다.
2. 낚시왕이 있는 열에서 가장 가까운 상어를 잡는다. 잡은 상어는 격자판에서 사라진다.
3. 상어들이 이동한다. 각 상어는 자신의 속력과 방향에 따라 이동하며, 격자판의 경계를 넘으면 방향을 반대로 바꾸며 이동을 계속한다.
4. 같은 칸에 여러 상어가 있다면 크기가 가장 큰 상어만 남고 나머지는 모두 사라진다.

낚시왕이 잡은 상어 크기의 합을 구하는 것이 목표이다.

입력 조건

• 첫째 줄에 격자판의 크기 R,C와 상어의 수 M이 주어진다. (2≤R,C≤100, 0≤M≤R×C)
• 다음 M개의 줄에는 상어의 정보가 주어진다.
  • r,c,s,d,z: 상어의 위치 (r,c), 속력 s, 이동 방향 d, 크기 z
  • 방향 d: 1(위), 2(아래), 3(오른쪽), 4(왼쪽)

문제 접근

이 문제는 시뮬레이션 문제로, 시간의 흐름에 따라 상태를 정확하게 업데이트해야 한다. 주요 고려 사항은 다음과 같다:

• 낚시왕의 이동 및 상어 낚시: 낚시왕은 매 시간마다 오른쪽으로 한 칸씩 이동하며, 현재 열에서 가장 가까운 상어를 잡는다.
• 상어의 이동: 각 상어는 자신의 속력과 방향에 따라 이동한다. 이동 중에 경계를 넘으면 방향을 반대로 바꾸며 이동한다.
• 상어의 겹침 처리: 이동 후 같은 칸에 여러 상어가 있다면 크기가 가장 큰 상어만 남긴다.

해결 방법

1. 데이터 구조 정의

• 상어의 위치와 정보를 저장하기 위해 딕셔너리를 사용한다.
• 키: 상어의 위치 (x,y)
• 값: [s,d,z](속력, 방향, 크기)

2. 방향 설정

• 방향은 다음과 같이 설정한다:
  • 0: 위 (−1,0)
  • 1: 아래 (1,0)
  • 2: 오른쪽 (0,1)
  • 3: 왼쪽 (0,−1)

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

3. 상어 이동 함수 구현

상어의 이동을 반복문 없이 수학적으로 계산한다.

• 상어의 이동 주기(cycle)를 계산한다.
  • 세로 이동 주기: cycle=2×(R−1)
  • 가로 이동 주기: cycle=2×(C−1)
• 속력을 주기로 나눈 나머지를 사용하여 실제 이동 거리를 계산한다.
• 경계를 넘으면 대칭 위치로 이동하고, 방향을 반대로 바꾼다.

def move_shark(x, y, s, d):
    if d == 0 or d == 1:  # 위 또는 아래
        cycle = 2 * (R - 1)
        s %= cycle
        for _ in range(s):
            x += dx[d]
            if x < 0 or x >= R:
                d = 1 - d
                x += 2 * dx[d]
    else:  # 오른쪽 또는 왼쪽
        cycle = 2 * (C - 1)
        s %= cycle
        for _ in range(s):
            y += dy[d]
            if y < 0 or y >= C:
                d = 5 - d
                y += 2 * dy[d]
    return x, y, d

하지만 위의 함수에서도 반복문이 사용되므로, 반복문을 제거하여 최적화한다.

def move_shark(x, y, s, d):
    if d == 0 or d == 1:  # 세로 이동
        cycle = 2 * (R - 1)
        s %= cycle
        if d == 0:
            x -= s
            if x < 0:
                x = -x
                d = 1
            if x >= R:
                x = cycle - x
                d = 0
        else:
            x += s
            if x >= R:
                x = cycle - x
                d = 0
            if x < 0:
                x = -x
                d = 1
    else:  # 가로 이동
        cycle = 2 * (C - 1)
        s %= cycle
        if d == 2:
            y += s
            if y >= C:
                y = cycle - y
                d = 3
            if y < 0:
                y = -y
                d = 2
        else:
            y -= s
            if y < 0:
                y = -y
                d = 2
            if y >= C:
                y = cycle - y
                d = 3
    return x, y, d

4. 시뮬레이션 진행

• 낚시왕은 왼쪽에서 시작하여 오른쪽으로 한 칸씩 이동한다.
• 각 열에서 가장 가까운 상어를 잡고, 잡은 상어의 크기를 누적한다.
• 상어들을 이동시키고, 이동 후 같은 위치에 있는 상어들은 크기를 비교하여 하나만 남긴다.

 

백준 17143 낚시왕 파이썬 정답 코드

import sys
input = sys.stdin.readline

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

sharks = dict()

for _ in range(M):
    r, c, s, d, z = map(int, input().split())
    sharks[(r - 1, c - 1)] = [s, d - 1, z]

dx = [-1, 1, 0, 0]  # 위, 아래, 오른쪽, 왼쪽
dy = [0, 0, 1, -1]

def move_shark(x, y, s, d):
    if d == 0 or d == 1:  # 세로 이동
        cycle = 2 * (R - 1)
        if cycle != 0:
            s %= cycle
        if d == 0:
            x -= s
            if x < 0:
                x = -x
                d = 1
            if x >= R:
                x = cycle - x
                d = 0
        else:
            x += s
            if x >= R:
                x = cycle - x
                d = 0
            if x < 0:
                x = -x
                d = 1
    else:  # 가로 이동
        cycle = 2 * (C - 1)
        if cycle != 0:
            s %= cycle
        if d == 2:
            y += s
            if y >= C:
                y = cycle - y
                d = 3
            if y < 0:
                y = -y
                d = 2
        else:
            y -= s
            if y < 0:
                y = -y
                d = 2
            if y >= C:
                y = cycle - y
                d = 3
    return x, y, d

total_catch = 0

for col in range(C):
    # 낚시왕이 있는 열에서 가장 가까운 상어 잡기
    min_row = R
    shark_pos = None
    for row in range(R):
        if (row, col) in sharks:
            if row < min_row:
                min_row = row
                shark_pos = (row, col)
    if shark_pos:
        total_catch += sharks[shark_pos][2]
        del sharks[shark_pos]

    # 상어 이동
    new_sharks = dict()
    for (x, y), (s, d, z) in sharks.items():
        nx, ny, nd = move_shark(x, y, s, d)
        if (nx, ny) in new_sharks:
            if new_sharks[(nx, ny)][2] < z:
                new_sharks[(nx, ny)] = [s, nd, z]
        else:
            new_sharks[(nx, ny)] = [s, nd, z]
    sharks = new_sharks

print(total_catch)

결론

이 문제는 시뮬레이션과 구현 능력을 요구하는 문제로, 각 단계에서 발생하는 상태 변화를 정확히 추적해야 한다. 특히, 상어의 이동에서 반복문을 제거하고 수학적인 계산으로 이동을 처리하여 시간 복잡도를 최적화해야 한다.

17143 백준 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.