[BOJ][Python] 17143번 낚시왕

1. 문제

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

 

---

2. 문제 풀이 알고리즘

R x C 칸에 상어가 m마리가 있고 상어는 각각 한 칸을 차지하고, 1초 동안 움직이는 속도 s, 방향 d에 따라서 d방향으로 1초 동안 s칸만큼 이동한다. 벽에 닿을 시에는 방향을 반대방향으로 움직인다.

 

낚시왕은 1번 열부터 시작하여 C열에 도달할 때까지 한 열에 있는 상어 중 가장 가까운 상어를 잡는다. 열을 한 번 움직일 때마다 1초가 소요된다. 이때 낚시왕이 C열에 도달하여 움직임을 멈출 때까지 잡은 상어의 크기의 합을 구해야한다.

 

이 문제를 해결하기 위해서는 현재 열에서 가장 가까운 상어를 찾음 → 상어를 잡음 → 남은 상어를 이동 이 세 가지를 모두 구현해야 한다.

 

---

3. 구현

1) 입력 받고 저장

r, c, m = map(int, sys.stdin.readline().strip().split())
shark = {}
shark_key = []
area = [[-1 for _ in range(c)] for _ in range(r)]

for i in range(m):
    r_s, c_s, s, d, z = map(int, sys.stdin.readline().strip().split())
    shark[z] = [r_s, c_s, s, d]
    area[r_s - 1][c_s - 1] = z
    shark_key.append(z)

shark_key.sort()
shark_key.reverse()

• shark (dict): 상어의 크기: [행, 열, 속도, 방향]을 저장해놓는 딕셔너리, 상어의 크기가 1부터 차례로 있는 것이 아니기 때문에 리스트의 인덱스로 접근하는 것보다는 딕셔너리로 접근하는 것이 더 낫지 않을까 판단했다.
• shark_key (list): 상어의 크기, 즉 shark 딕셔너리의 키를 저장해놓는 리스트, 따로 리스트로 만들어준 이유는 1초 후 상어의 위치를 바꿀 때 이전의 위치에 영향을 받지 않기 위해서 상어의 크기가 큰 것부터 옮겨주고, 또 shark 딕셔너리를 상어가 잡힐 때마다 없애지 않고 shark_key만 초기화하여 사용하기 위해서다. 상어 정보를 모두 입력받은 후 내림차순 정렬을 하기 위하여 sort, reverse 해주었다.
• area (list): 상어가 있는 R x C 칸을 표현한 리스트, 상어가 없는 공간은 -1, 있는 공간은 해당 공간에 존재하는 상어의 크기를 넣어주었다.

 

2) 함수구현

import sys

def next_area(key):
    row, col, s, d = shark[key]
    if area[row - 1][col - 1] == key:
        area[row - 1][col - 1] = -1

    if d == 1:
        if s > row - 1:
            s = s - (row - 1)
            div = s // (r - 1)
            mod = s % (r - 1)

            if div % 2 == 0:
                shark[key][0] = 1 + mod
                shark[key][3] = 2
            else:
                shark[key][0] = r - mod
                
        else:
            shark[key][0] = row - s


    if d == 2:
        if row + s > r - 1:
            s = s - (r - row)
            div = s // (r - 1)
            mod = s % (r - 1)

            if div % 2 == 0:
                shark[key][0] = r - mod
                shark[key][3] = 1
            else:
                shark[key][0] = 1 + mod
                

        else:
            shark[key][0] = row + s

    if d == 3:
        if col + s > c - 1:
            s = s - (c - col)
            div = s // (c - 1)
            mod = s % (c - 1)

            if div % 2 == 0:
                shark[key][1] = c - mod
                shark[key][3] = 4
            else:
                shark[key][1] = 1 + mod

        else:
            shark[key][1] = col + s

    if d == 4:
        if s > col - 1:
            s = s - (col - 1)
            div = s // (c - 1)
            mod = s % (c - 1)

            if div % 2 == 0:
                shark[key][1] = 1 + mod
                shark[key][3] = 3
            else:
                shark[key][1] = c - mod

        else:
            shark[key][1] = col - s

    if area[shark[key][0] - 1][shark[key][1] - 1] < key:
        area[shark[key][0] - 1][shark[key][1] - 1] = key
        return True
    return False

def move_shark(k):
    global shark_key
    new_key = []

    for key in shark_key:
        if key == k:
            continue
        if next_area(key):
            new_key.append(key)
    
    
    shark_key = new_key


def catch_shark(key):
    area[shark[key][0] - 1][shark[key][1] - 1] = -1
    return key


def fishing():
    result = 0
    for j in range(c):
        key = -1
        for i in range(r):
            if area[i][j] != -1:
                key = area[i][j]
                result += catch_shark(area[i][j])
                break
        
        move_shark(key)

    return result

• fishing()
  • 열을 처음부터 끝까지 탐색하며 가장가까운 상어를 찾으면 key의 값을 해당 상어의 크기로 설정해주었다.
  • catch_shark 함수를 호출하여 해당 상어에 대한 정보를 없애주고, move_shark 함수를 사용하여 잡힌 상어를 제외한 나머지 상어를 1초 이후의 자리로 셋팅해주도록 하였다.
• catch_shark(key)
  • key에 해당하는 잡힌 상어의 정보를 없애주는 함수, area에서 해당 위치에 상어의 크기를 -1로 초기화해준다.
• move_shark(k)
  • shark_key 리스트에서 잡힌 상어 k를 빼주고, 잡힌 상어를 제외한 각 상어들을 1초 이후의 위치로 설정
  • next_area(key)를 호출하여 상어를 1초 이후의 위치로 셋팅해주고, 다른 큰 상어에게 잡힌경우 False를 반환받으므로 그 때는 shark_key에서 해당 key를 제외한다.
• next_area(key)
  • key에 해당하는 상어의 현재 위치를 초기화해주고, 방향과 속도에 맞는 위치를 계산하여 해당 위치에 상어가 없을 때나 더 작은 상어가 있을 때 해당 위치에 상어를 배치한다.
  • 상어의 다음 위치는 몫, 나머지 연산으로 구했는데 이렇게 하면 시간면에서 효율적으로 할 수 있다. 속도만큼 while문을 돌려준 사람들도 있는데 시간초과가 났다고 한다.
  • 상어가 잡아먹히지 않은 경우 True 먹히면 False를 반환한다.