BOJ 17143 낚시왕 - Python

티어
골드 1

문제 링크 ( 제출 : PyPy )
https://www.acmicpc.net/problem/17143

바로 전 포스팅도 물고기랑 상어였는데, 어쩌다 보니 또 상어가 나왔다.

풀이

단순 구현 문제이다.
1. 낚시꾼은 시간이 지남에 따라, 한 칸씩 오른쪽으로 이동한다.
2. 낚시꾼과 제일 가까운 상어 즉, x좌표가 가장 작은 상어를 낚시꾼이 잡는다.
3. 상어들이 속력과, 방향을 가지고 이동한다. ( 이 때, 겹친 상어는 크기가 큰 상어에게 먹힌다. )

중요한 점
상어를 이동시킬 때, 한 칸씩 이동시키게 되면 s의 최댓값이 1000이기 때문에,
R_MAX ( 100 ) * R_MAX ( 100 ) * C_MAX ( 100 ) * S_MAX ( 1000 )
= 1,000,000,000이 되어, 1초안에 통과하지 못한다.
따라서, 좌표를 한 칸씩 움직이는 계산 말고 다른 방법을 찾아야 한다.

좌표 계산 방법
( 1, 3 ) 의 아래로 향하는 상어를 예시로 들겠다.

해당 상어가, 이동 후에 다시 원래 자리로 돌아올 수 있는 시간을 계산하면 S가 아무리 크더라도 O(R_MAX)안에 계산할 수 있다.
예시 변수들 : R = 4, Shark(1, 3), Speed = 5

방향이 1 or 2 일 때 다시 제자리로 돌아오는 경우 : (R-1) * 2
방향이 3 or 4 일 때 : (C-1) * 2

따라서, 현재 상어의 x 또는 y를 해당 값으로 나눠주면 제자리로 돌아오는 연산을 모두 제외하고 나머지 경우만 이동시킬 수 있다.

Ex ( 0 0 1 ) 에서 왼쪽으로 5번 이동

(3-1) * 2 = 4

1. 0 1 0
2. 1 0 0
3. 0 1 0
4. 0 0 1 -> 여기까지 계산했을 때 똑같이 돌아오므로 계산해 줄 필요가 없다. 1번 계산한 결과와 동일.
5. 0 1 0

move_cnt = shark.speed % ((R-1)\*2) # direction in [1, 2]
move_cnt = shark.speed % ((C-1)\*2) # direction in [3, 4]

실수할 만한 점
상어가 벽을 넘어갔을 경우,
Ex x < 0 이 됐을 때, 방향을 바꾸고 +1을 해 주면 다시 0이 된다.
0이 아닌 1로 이동해야 하므로 +2를 해줘야 한다. ( 다른 모든 경우도 마찬가지 )

코드 설명

Shark Class

class Shark:

  def __init__(self, speed, direction, size):
    self.speed = speed
    self.direction = direction
    self.size = size

상어 이동 함수

def move_shark():
  global board # 상어를 담아 놓는 board
  
  # 중복되는 상어들을 체크하기 위한 새로운 board
  temp_board = [[None for _ in range(C)] for _ in range(R)]

  for i in range(R):
    for j in range(C):
      # 상어가 없는 경우
      if board[i][j] is None: continue

      move_cnt = None
      temp_x, temp_y = i, j
      shark = board[i][j]

      # direction이 1, 2이면, (R-1) * 2를 사용한다.
      if shark.direction in [1, 2]:
        move_cnt = shark.speed % ((R-1)*2) # 계산 필요 횟수

        for _ in range(move_cnt):
          temp_x += dx[shark.direction]
		
          # 범위에서 벗어났다면, direction을 바꿔주고 
          # 잘못 연산된 +1과 -1을 바로잡기 위해 +2, -2
          if temp_x < 0:
            shark.direction = 2
            temp_x += 2 # -1 이 아닌, 1로 갔어야 하므로 +2
          if temp_x >= R:
            shark.direction = 1
            temp_x -= 2 # R이 아닌, R-2로 갔어야 하므로 -2
            
      # direction이 3, 4이면, (C-1) * 2를 사용한다.
      else:
        move_cnt = shark.speed % ((C-1)*2)
        for _ in range(move_cnt):
          temp_y += dy[shark.direction]

          if temp_y < 0:
            shark.direction = 3
            # -1 이 아닌, 1로 갔어야 하므로 +2
            temp_y += 2
          if temp_y >= C:
            shark.direction = 4
            temp_y -= 2

      # 이미 존재하는 상어의 사이즈가 더 크다 -> 잡아 먹힘 -> 동작 X
      if temp_board[temp_x][temp_y] and temp_board[temp_x][temp_y].size > shark.size:
          continue
      
      # None 이거나, 내가 더 크므로 나로 할당한다.
      temp_board[temp_x][temp_y] = shark
    
  # 기존 board를 temp_board로 초기화.
  board = temp_board

사용자 input 및 낚시꾼 이동 처리

R, C, M = map(int, get().split())
board = [[None for _ in range(C)] for _ in range(R)]
answer = 0

# direction에 따른 이동 방향
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]

for _ in range(M):
  x, y, s, d, z = map(int, get().split())
  x -= 1
  y -=1
  shark = Shark(s, d, z)
  board[x][y] = shark

# 시간은 필요 없고, 낚시꾼이 이동하는 경로만 체크해 주면 된다.
for i in range(C):

  # 가장 가까운 상어 찾기. == x 좌표가 가장 작은 것
  for x_idx in range(R):

    if board[x_idx][i]:
      answer += board[x_idx][i].size
      board[x_idx][i] = None
      
      break

  move_shark()
  
print(answer)

그 외 풀이

board에 상어들을 담는 것이 아닌, 상어위치가 담겨있는 리스트만으로도 해결이 가능할 것 같다.
다만 같은 칸에 상어가 있는지 검사하고, x 좌표를 기준으로 정렬하는 작업이 필요해서 비슷비슷 할 것 같다.

전체 코드

import sys

def get():
  return sys.stdin.readline().rstrip()

class Shark:

  def __init__(self, speed, direction, size):
    self.speed = speed
    self.direction = direction
    self.size = size

def move_shark():
  global board
  
  temp_board = [[None for _ in range(C)] for _ in range(R)]

  for i in range(R):
    for j in range(C):
      # 상어가 없는 경우
      if board[i][j] is None: continue

      move_cnt = None
      temp_x, temp_y = i, j
      shark = board[i][j]

      # 처음 자기 자리로 돌아오는 경우
      if shark.direction in [1, 2]:
        move_cnt = shark.speed % ((R-1)*2)

        for _ in range(move_cnt):
          temp_x += dx[shark.direction]

          if temp_x < 0:
            shark.direction = 2
            # -1 이 아닌, 1로 갔어야 하므로 +2
            temp_x += 2
          if temp_x >= R:
            shark.direction = 1
            temp_x -= 2
      else:
        move_cnt = shark.speed % ((C-1)*2)
        for _ in range(move_cnt):
          temp_y += dy[shark.direction]

          if temp_y < 0:
            shark.direction = 3
            # -1 이 아닌, 1로 갔어야 하므로 +2
            temp_y += 2
          if temp_y >= C:
            shark.direction = 4
            temp_y -= 2

      # 이미 존재하는 상어의 사이즈가 더 큼 -> 잡아 먹힘
      if temp_board[temp_x][temp_y] and temp_board[temp_x][temp_y].size > shark.size:
          continue
          
      temp_board[temp_x][temp_y] = shark

  board = temp_board

R, C, M = map(int, get().split())
board = [[None for _ in range(C)] for _ in range(R)]
answer = 0
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]

for _ in range(M):
  x, y, s, d, z = map(int, get().split())
  x -= 1
  y -=1
  shark = Shark(s, d, z)
  board[x][y] = shark


for i in range(C):
  
  for x_idx in range(R):

    if board[x_idx][i]:
      answer += board[x_idx][i].size
      board[x_idx][i] = None
      
      break

  move_shark()
  
print(answer)