[백준] 17143 낚시왕 (파이썬)

골드 Ⅰ

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

17143번: 낚시왕

 

📄 문제

• 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다.
• 격자판의 각 칸은 (r, c)로 나타낼 수 있다.
• r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
• 칸에는 상어가 최대 한 마리 들어있을 수 있다.
• 상어는 크기와 속도를 가지고 있다.
• 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다.
• 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다.
  1. 낚시왕이 오른쪽으로 한 칸 이동한다.
  2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
  3. 상어가 이동한다.
• 상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다.
• 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한 채로 이동한다.
• 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.
• 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

 

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

 

---

💡 아이디어

• 구현 문제이다. 주어진 문제의 순서에 따라 구현하면 된다.
• 낚시왕이 같은 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는 함수가 필요하다.
• 낚시왕이 잡은 상어 크기의 합을 저장할 변수도 필요하다.
• 상어가 이동하는 함수가 필요하다.
• 상어가 이동을 후, 한 칸에 상어가 두 마리 이상 있을 때 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는 함수 또는 알고리즘이 필요하다.

 

• 따라서, 아래의 순서로 알고리즘을 구현하면 된다.
  1. 낚시왕이 전체 열을 순차적으로 탐색한다. (이동한다.)
  2. 열을 이동할 때마다, 해당 열을 탐색하여 땅과 제일 가까운 상어를 잡아 크기를 저장한다.
  3. 낚시 후, 전체 상어를 차례대로 주어진 방향과 속도로 이동시킨다.
  4. 이동 중, 격자판의 경계를 만나면 방향을 반대로 바꿔서 계속 이동한다.
  5. 이동한 상어는 새로운 격자판의 이동 위치에 속도, 방향, 크기를 저장한다.
  6. 열을 차례대로 탐색하면서 2,3,4,5번을 반복한다. 
  7. 모든 상어가 이동한 후 또는 이동 중 일 때, 새로운 격자판의 같은 칸에 이동한 상어가 두 마리 이상 존재하면 가장 큰 상어만 남긴다.

 

---

상어를 이동 시키는 방법과 같은 칸에 가장 큰 상어만 남기는 방법을 두가지로 풀이했다.

 

상어를 이동 시키는 방법 (새로운 격자판에 위치 저장)

1. 반복문을 활용하여, 해당 속도와 방향으로 한 칸씩 이동시킨다.
   • 한 칸씩 이동하면서 경계를 만나면 방향을 바꿔 이동한다.
2. 이동이 끝난 위치를 미리 계산하여 바로 저장한다. ✅
   • 바뀐 위치와 방향을 격자판의 개수와 속도를 이용하여 미리 계산한다.

 

가장 큰 상어만 남기는 방법

1. 모든 상어의 이동이 끝난 후
   • 모든 상어를 차례대로 이동시킨다.
   • 새로운 격자판에 이동한 상어를 저장한다.
   • 모든 상어의 이동이 끝난 후 새로운 격자판을 전체 탐색한다.
   • 같은 칸에 상어가 두 마리 이상일 때 가장 큰 상어만 남기고 나머지 상어는 제거한다.
2.  상어가 이동 중 일 때 ✅
   • 모든 상어를 차례대로 이동시킨다.
   • 새로운 격자판에 이동한 상어를 저장한다.
   • 저장 전에, 해당 칸에 이미 이동한 상어가 있는지 확인한다.
   • 상어가 없으면 그대로 저장하고
   • 상어가 있으면 크기를 비교해 큰 상어로 바꿔 저장한다.

 

📝 문제 풀이 (Code)

최종 코드 ( 실행시간 264ms, 메모리 127052 KB, PyPy3 )

• 상어를 이동시킬 때, 이동이 끝난 위치를 미리 계산하여 새로운 격자판에 바로 저장한다.
• 상어가 이동할 때, 새로운 격자판에 이미 이동한 상어가 존재하면 상어의 크기를 비교하여 큰 상어만 남긴다.

import sys
input = sys.stdin.readline

def move_shark():
    # 이동한 상어 저장
    ocean = [[False]*c for _ in range(r)]
    # 전체 상어 이동
    for x in range(r):
        for y in range(c):
            if sea[x][y]:
                s, d, z = sea[x][y]
                nx = x + di[d] * s
                ny = y + dj[d] * s

                # 위아래
                if d == 1 or d == 2:
                    quota = nx // (r-1)
                    remainder = nx % (r-1)
                    # 같은 방향
                    if quota % 2 == 0:
                        nx = remainder
                    # 방향 전환
                    else:
                        d = boundary[d]
                        nx = (r - 1) - remainder
                # 좌우
                else:
                    quota = ny // (c-1)
                    remainder = ny % (c-1)
                    # 같은 방향
                    if quota % 2 == 0:
                        ny = remainder
                    # 방향 전환
                    else:
                        d = boundary[d]
                        ny = (c - 1) - remainder
                # 큰 상어만 남기기
                if not ocean[nx][ny] or ocean[nx][ny][2] < z:
                    ocean[nx][ny] = (s, d, z)
    return ocean


def catch_shark(j):
    global sea
    # 행 탐색
    for i in range(r):
        if sea[i][j]:
            # 상어를 잡는다.
            s, d, z = sea[i][j]
            sea[i][j] = False
            return z
    return 0


# 격자판의 크기 R, C와 상어의 수 M
r, c, m = map(int, input().split())
sea = [[False]*c for _ in range(r)]

# d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽
di = [0, -1, 1, 0, 0]
dj = [0, 0, 0, 1, -1]
boundary = {1:2, 2:1, 3:4, 4:3}

for _ in range(m):
    # (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기
    rr, cc, s, d, z = map(int, input().split())
    sea[rr-1][cc-1] = (s, d, z)

fishing = 0
for j in range(c):
    # 낚시
    fishing += catch_shark(j)
    # 상어 이동
    sea = move_shark()
print(fishing)

 

처음 코드 ( 실행시간 2876 ms, 메모리 224452 KB, PyPy3)

• 상어를 이동 시킬때, 반복문을 활용하여 해당 속도와 방향으로 한 칸씩 이동시킨다.
• 모든 상어의 이동이 끝난 후, 격자판을 탐색하여 같은 칸에 2마리 이상 존재할 때 큰 상어만 남긴다. 

import sys
input = sys.stdin.readline

def move_shark():
    ocean = [[[] for _ in range(c)] for _ in range(r)]
    # 전체 상어 이동
    for row in range(r):
        for col in range(c):
            if sea[row][col]:
                z, s, d = sea[row][col][0]
                x = row
                y = col
                go = 0
                # 상어 속도 만큼 이동
                while go < s:
                    nx = x + di[d]
                    ny = y + dj[d]
                    if 0 <= nx < r and 0 <= ny < c:
                        x, y = nx, ny
                        go += 1
                    # 벽과 충돌, 방향전환
                    else:
                        d = boundary[d]
                        continue
                ocean[x][y].append((z, s, d))
    return ocean


def shark_eat():
    global sea
    for row in range(r):
        for col in range(c):
            # 한 칸에 상어가 2마리 이상 있는 경우
            if 1 < len(sea[row][col]):
                sea[row][col].sort(reverse=True)
                sea[row][col] = [sea[row][col][0]]


def catch_shark(j):
    global sea
    # 행 탐색
    for i in range(r):
        if sea[i][j]:
            # 상어를 잡는다.
            z, s, d = sea[i][j].pop()
            return z
    return 0


# 격자판의 크기 R, C와 상어의 수 M
r, c, m = map(int, input().split())
sea = [[[] for _ in range(c)] for _ in range(r)]

# d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
di = [0, -1, 1, 0, 0]
dj = [0, 0, 0, 1, -1]
boundary = {1:2, 2:1, 3:4, 4:3}

for _ in range(m):
    # (rr, cc)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다.
    rr, cc, s, d, z = map(int, input().split())
    sea[rr-1][cc-1].append((z, s, d))

fishing = 0
for j in range(c):
    # 낚시
    fishing += catch_shark(j)
    # 상어가 이동한다.
    sea = move_shark()
    # 큰 상어가 먹는다
    shark_eat()
print(fishing)

 

두 번째 코드 ( 실행시간 2804 ms, 메모리 223112 KB, PyPy3 )

처음 코드와 다른 점은 상어가 이동을 마친 후에 한 칸에 두 마리 이상 있을 때, 가장 큰 상어를 남기는 방법을 다르게 구현하였다. (각 상어가 이동할 때, 전체 상어 이동 후)

• 상어가 이동할 때,  이미 이동한 상어가 존재하면 상어의 크기를 비교하여 큰 상어만 남긴다. (이동 중에 비교)

import sys
input = sys.stdin.readline

def move_shark():
    ocean = [[[] for _ in range(c)] for _ in range(r)]
    # 전체 상어 이동
    for row in range(r):
        for col in range(c):
            if sea[row][col]:
                s, d, z = sea[row][col][0]
                x = row
                y = col
                go = 0
                # 상어 속도 만큼 이동
                while go < s:
                    nx = x + di[d]
                    ny = y + dj[d]
                    # 맵 내부에서 이동하는 경우
                    if 0 <= nx < r and 0 <= ny < c:
                        x, y = nx, ny
                        go += 1
                    # 벽과 충돌하는 경우, 방향전환
                    else:
                        d = boundary[d]
                        continue

                # 큰 상어만 남기기
                if not ocean[x][y] or ocean[x][y][0][2] < z:
                    ocean[x][y] = [(s, d, z)]

    return ocean


def catch_shark(j):
    global sea
    # 행 탐색
    for i in range(r):
        if sea[i][j]:
            # 상어를 잡는다.
            s, d, z = sea[i][j].pop()
            return z
    return 0


# 격자판의 크기 R, C와 상어의 수 M
r, c, m = map(int, input().split())
sea = [[[] for _ in range(c)] for _ in range(r)]

# d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
di = [0, -1, 1, 0, 0]
dj = [0, 0, 0, 1, -1]
boundary = {1:2, 2:1, 3:4, 4:3}

for _ in range(m):
    # (rr, cc)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다.
    rr, cc, s, d, z = map(int, input().split())
    sea[rr-1][cc-1].append((s, d, z))

fishing = 0
for j in range(c):
    # 낚시
    fishing += catch_shark(j)
    # 상어가 이동한다.
    sea = move_shark()
print(fishing)