[알고리즘] 백준#17143: 낚시왕/Python

📝 문제

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

17143번: 낚시왕

💡 접근법

문제에 주어진 조건을 빠짐 없이 고려하여 구현해야 정답을 맞출 수 있습니다. 낚시왕이 컬럼(column) 방향으로 움직이므로 컬럼을 기준으로 전체 로직이 수행됩니다. 컬럼이 결정되면 로우(row) 방향으로 상어가 있는지 탐색하고, 가장 작은 로우에 있는 상어를 낚습니다. 상어의 진행방향을 고려하여 상어의 속도까지 한 칸씩 이동시키며 상어가 이동 가능한지 체크합니다. 만약 같은 좌표에 2마리 이상의 상어가 있을 경우 크기가 작은 상어가 제거됩니다. 이를 위해, 상어 정보를 저장하는 리스트에서 상어의 무게가 큰 순서로 정렬하고, 하나의 좌표에 가장 사이즈가 큰 상어 한 마리만 남을 때까지 리스트에서 원소를 pop합니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline

# 상어 이동 함수
def move_shark():
    g = [[[] for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if graph[i][j]:
                x, y = i, j
                s, d, z = graph[i][j][0]
                dist = s
                # 상어의 속도만큼 1칸씩 이동
                while 0 < dist:
                    nx = x + direction[d][0]
                    ny = y + direction[d][1]
                    # 맵 내부에서 이동하는 경우
                    if 0 <= nx < R and 0 <= ny < C:
                        x, y = nx, ny
                        dist -= 1 # 이동해야 할 남은 거리 1 차감
                    # 벽과 충돌하는 경우, 현재 진행방향별 방향전환
                    else:
                        # d(0-1-2-3) : 방향(상-하-우-좌)
                        # 상 to 하 or 우 to 좌
                        if d == 0 or d == 2:
                            d += 1
                        # 하 to 상 or 좌 to 우
                        elif d == 1 or d == 3:
                            d -= 1
                        continue
                g[x][y].append([s, d, z])

    for i in range(R):
        for j in range(C):
            graph[i][j] = g[i][j]

# 상어 낚시 함수
def catch_shark():
    global answer
    # 낚시왕이 칼럼 방향으로 이동하며 낚시를 하기 때문에 칼럼 우선순위
    for i in range(C):
        for j in range(R):
            # 상어가 존재하는 경우
            if graph[j][i]:
                answer += graph[j][i][0][2]
                graph[j][i].remove(graph[j][i][0])
                break

        move_shark()
        for m in range(R):
            for n in range(C):
                # 한 좌표에 상어가 2마리 이상 있는 경우
                if 1 < len(graph[m][n]):
                    # 몸집이 작은 순서대로 상어 제거
                    graph[m][n].sort(key=lambda x: x[2], reverse=True)
                    while 1 < len(graph[m][n]):
                        graph[m][n].pop()

if __name__ == '__main__':
    R, C, M = map(int, input().split())
    # 진행방향: 상, 하, 우, 좌
    direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    graph = [[[] for _ in range(C)] for _ in range(R)]
    for _ in range(M):
        r, c, s, d, z = map(int, input().split())
        graph[r-1][c-1].append([s, d-1, z])

    answer = 0
    catch_shark()
    print(answer)

2) 해설

(1) 라이브러리 import

import sys; input = sys.stdin.readline
from itertools import combinations

• sys 모듈
  • 파이썬 내장 함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline 사용

(2) main 함수

if __name__ == '__main__':
    R, C, M = map(int, input().split())
    # 진행방향: 상, 하, 우, 좌
    direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    graph = [[[] for _ in range(C)] for _ in range(R)]
    for _ in range(M):
        r, c, s, d, z = map(int, input().split())
        graph[r-1][c-1].append([s, d-1, z])

    answer = 0
    catch_shark()
    print(answer)

 

문제에서 행과 열의 번호가 $0$부터 시작하는 인덱스와 달리 $1$부터 시작하기 때문에, 인덱스에 맞추기 위해 입력된 상어의 좌표 값을 $1$씩 뺀 값으로 저장합니다.

(3) 상어 낚시 함수

# 상어 낚시 함수
def catch_shark():
    global answer
    # 낚시왕이 칼럼 방향으로 이동하며 낚시를 하기 때문에 칼럼 우선순위
    for i in range(C):
        for j in range(R):
            # 상어가 존재하는 경우
            if graph[j][i]:
                answer += graph[j][i][0][2]
                graph[j][i].remove(graph[j][i][0])
                break

        move_shark()
        for m in range(R):
            for n in range(C):
                # 한 좌표에 상어가 2마리 이상 있는 경우
                if 1 < len(graph[m][n]):
                    # 몸집이 작은 순서대로 상어 제거
                    graph[m][n].sort(key=lambda x: x[2], reverse=True)
                    while 1 < len(graph[m][n]):
                        graph[m][n].pop()

낚시왕이 컬럼 방향으로 이동하며 낚시를 하기 때문에 컬럼을 기준으로 로직이 동작합니다. 컬럼이 결정되면 로우 방향으로 [0] 인덱스부터 가장 가까운 곳에 있는 상어를 낚습니다. 상어를 이동시키고 한 좌표에 여러 마리가 있을 경우 $1$마리만 남을 때까지 몸집이 작은 상어는 제거합니다. 이를 위해 상어 정보를 저장한 리스트를 상어의 크기에 따라 정렬하였습니다. pop 메서드를 활용하여 몸집이 작은 상어를 제거하기 위해 역순으로 정렬하였습니다.

(4) 상어 이동 함수

# 상어 이동 함수
def move_shark():
    g = [[[] for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if graph[i][j]:
                x, y = i, j
                s, d, z = graph[i][j][0]
                dist = s
                # 상어의 속도만큼 1칸씩 이동
                while 0 < dist:
                    nx = x + direction[d][0]
                    ny = y + direction[d][1]
                    # 맵 내부에서 이동하는 경우
                    if 0 <= nx < R and 0 <= ny < C:
                        x, y = nx, ny
                        dist -= 1 # 이동해야 할 남은 거리 1 차감
                    # 벽과 충돌하는 경우, 현재 진행방향별 방향전환
                    else:
                        # d(0-1-2-3) : 방향(상-하-우-좌)
                        # 상 to 하 or 우 to 좌
                        if d == 0 or d == 2:
                            d += 1
                        # 하 to 상 or 좌 to 우
                        elif d == 1 or d == 3:
                            d -= 1
                        continue
                g[x][y].append([s, d, z])

    for i in range(R):
        for j in range(C):
            graph[i][j] = g[i][j]

상어 이동 함수입니다. 상어별로 속도만큼 $1$칸씩 진행방향으로 이동시킵니다. 이동할 좌표가 맵에서 벗어난 경우 진행 방향의 반대 방향으로 방향을 전환해 줍니다.

📝 채점 결과

정답 확인

PyPy3로 제출하여 패스하였습니다.

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/implement/boj_17143.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.