[python] BOJ 백준 17143: 낚시왕

1. 문제  

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다. 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

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

2. 입력   

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

3. 출력   

낚시왕이 잡은 상어 크기의 합을 출력한다.

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 낚시왕이 오른쪽으로 한칸 이동하여 땅과 제일 가까운 상어를 잡는 catch함수와, 상어가 이동하는 move함수로 나누어 따로 구현해주었다. 격자판 배열을 하나 만들어서 해당 x,y좌표에 상어의 속력, 이동방향, 크기 배열을 저장해주었다. 이동방향은 상-하-우-좌 로 설정해주어야 문제의 조건과 일치한다. 

1) catch 함수: 상어를 잡을 열의 번호를 입력으로 받고 , 행은 for문을 돌면서 땅에서 제일 가까운 상어가 등장하면 그 상어를 잡고 반복문을 탈출한다. 상어의 위치에 해당하는 배열은 빈배열로 만들어주고, 해당 상어의 크기와 함께 리턴해준다. 상어가 잡히지 않을수도 있으므로 만약 상어가 없다면 0을 리턴해주어야한다. 

2) move함수: 새로운 임시 배열을 만들어서 상어정보를 저장해야한다. 기존배열에 적용할 경우 반복문을 돌면서 탐색했던 상어를 또 탐색하게 될수 있고, 2마리 이상 겹치는 칸에 대해서 제대로 계산을 해주지 못하게 된다. 상어이동은 해당 속력만큼 while문을 돌면서 경계를 넘어가면 방향을 바꾸어주고, 아니라면 x,y좌표를 해당 방향에 맞게 변화시켜주면된다. while문이 끝나면 임시배열에 해당 상어의 최종위치를 저장해준다. 모든 상어에 대한 이동이 끝났으면, 임시배열을 돌면서 한칸에 2마리 이상의 상어가 있는 칸들을 탐색하여 한마리로 만들어준다. 크기가 가장 큰 상어만 남기면 되므로 sort함수를 사용해 정렬해주면된다.   

5) 구현코드   

r,c,m=map(int,input().split())
board=[[[]for _ in range(c)] for _ in range(r)] #격자판 
for _ in range(m):
  x,y,s,d,z=map(int,input().split())
  board[x-1][y-1].append([s,d-1,z]) #속력, 이동방향, 크기 저장 

#상하우좌
dx=[-1,1,0,0]
dy=[0,0,1,-1]

#낚시왕이 상어 잡음 
def catch(y,board):
  answer=0 #잡은 물고기 크기 
  for i in range(r):
    if board[i][y]: #땅과 제일 가까운 상어 
      answer=board[i][y][0][2] #크기 
      board[i][y]=[] #배열 초기화 
      break
  return answer,board #크기, 배열 

#상어 이동 
def move(board):
  #상어가 이동한 임시배열 
  temp=[[[]for _ in range(c)] for _ in range(r)] 
  for i in range(r):
    for j in range(c):
      if board[i][j]: 
        x,y=i,j 
        s,d,z=board[i][j][0]
        dis=s #거리
        while dis: #속력만큼 이동할때까지 
          x,y=x+dx[d],y+dy[d]
          if 0<=x<r and 0<=y<c: #범위 안에서는 
            dis-=1 #거리1씩이동 
          else: #범위 벗어나면 
            x,y=x-dx[d],y-dy[d] #다시 빼주고 
            #방향전환 
            if d==0: d=1
            elif d==1: d=0
            elif d==2: d=3
            elif d==3: d=2
        temp[x][y].append([s,d,z]) #최종위치 업데이트 

  for i in range(r):
    for j in range(c):
      if len(temp[i][j])>=2: #2개이상의 상어가 한칸에 있으면 
      #제일 큰 상어만 남기기 
        temp[i][j].sort(key=lambda x:x[2], reverse=True)
        s,d,z=temp[i][j][0] 
        temp[i][j]=[[s,d,z]]
  return temp

shark=0 #잡은 상어 크기 
for i in range(c):
  eat,board=catch(i,board)
  shark+=eat
  board=move(board)

print(shark)

 

⭐️난이도:  골드 2  ⭐️

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

17143번: 낚시왕