[백준] 17143 낚시왕

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

좌표별로 상어의 정보를 기록하고 관리를 잘하는 것이 중요했습니다.

2차원 배열을 생성하고 낚시왕의 이동이 진행될 때마다 모든 좌표를 탐색하는 방법은 시간이 오래 걸려 비효율적이라 생각하였습니다.

그리하여 상어들의 정보를 딕셔너리(객체) 형태로 관리하였습니다.

상어의 좌표를 키로 하고, 속력/방향/크기 의 정보는 값으로 지정하였습니다.

 

상어를 잡는 것과 낚시왕의 이동은 어렵지 않았는데, 상어들의 속력에 따라 좌표 이동을 계산하는 규칙을 찾는 것이 어려웠습니다.

상어는 진행방향으로 주어진 속력의 칸만큼 이동이 되는데, (행 또는 열의 크기 - 1) * 2 의 속력을 갖게 되면 제자리로 돌아오는 규칙이 있습니다.

문제 예제 1번의 상황을 보면 B상어가 수직으로 이동하여, (4(행의 크기) - 1) * 2 => 6의 속력을 갖게 된다면 제자리로 돌아오게 됩니다.

이를 이용하여 큰 수의 속력이 주어졌을때 나머지만 이용하여 상어의 움직임을 계산하였습니다.

2) 알고리즘

• 구현

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def move_shark(sharks):
    moved_sharks = {}                               # 상어들 이동 후 정보

    for k, v in sharks.items():
        r, c = k                                    # 상어 좌표
        s, d, z = v                                 # 상어 정보

        if d < 2:                                   # 상하 이동
            r += dr[d] * s                     # 나머지 값만큼 추가 이동
            while r < 0 or r >= R:                  # 좌표 범위를 벗어나는 경우
                if r < 0:                           # 반대방향으로 이동
                    r *= -1
                elif r >= R:
                    r = 2 * R - r - 2
                d = 1 if d == 0 else 0              # 방향 전환

        elif d >= 2:                                # 좌우 이동
            c += dc[d] * s
            while c < 0 or c >= C:
                if c < 0:
                    c *= -1
                elif c >= C:
                    c = 2 * C - c - 2
                d = 3 if d == 2 else 2
        
        if moved_sharks.get((r, c), False):             # 같은 좌표에 이미 상어가 있는 경우
            if moved_sharks[(r, c)][2] < z:             # 현재 상어 크기가 더 클때만
                moved_sharks[(r, c)] = (s, d, z)        # 현재 상어로 덮어씌우기
        else:                                           # 좌표에 상어가 없다면
            moved_sharks[(r, c)] = (s, d, z)            # 상어 추가
    
    return moved_sharks                                 # 새로운 상어 정보 반환

dr = [-1, 1, 0, 0]                                          # 위, 아래, 오른쪽, 왼쪽
dc = [0, 0, 1, -1]

R, C, M = map(int, sys.stdin.readline().split())            # 행, 열 크기, 상어 수
sharks = {}                                                 # 상어들 위치 및 정보
answer = 0
king = 0                                                    # 낚시왕의 위치

for _ in range(M):
    r, c, s, d, z = map(int, sys.stdin.readline().split())  # 좌표, 속력, 이동 방향, 크기
    s %= (R-1) * 2 if d <=2 else (C-1) * 2                  # (이동할 칸 - 1) * 2 로 나눈다
    sharks[(r-1, c-1)] = (s, d-1, z)                        # 좌표를 키로 하고 값은 상어의 정보

while king < C:                                             # 낚시왕이 열을 한칸씩 이동하며 확인
    # 낚시왕과 같은 열에 있는 상어들을 찾은 후, 행의 번호가 낮은 순서대로 나열
    can_catch = sorted(filter(lambda x: x[1] == king, sharks.keys()), key=lambda x: x[0])

    if can_catch:                   # 잡을 수 있는 상어가 있다면
        coor = can_catch[0]         # 가장 낮은 행의 상어 좌표 선택
        answer += sharks[coor][2]   # 상어 잡기
        sharks.pop(coor)            # 상어 삭제
        
    sharks = move_shark(sharks)     # 상어 이동

    king += 1                       # 낚시왕 이동

print(answer)

---

🔗 문제 링크

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

17143번: 낚시왕

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다