문제 링크
https://www.acmicpc.net/problem/17143
🕒 Python 풀이시간: 1시간 20분
import sys
input = sys.stdin.readline
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]
R, C, M = map(int, input().split())
sharksInfo = dict()
board = [[0] * (C + 1) for _ in range(R + 1)]
numbering = 1
for _ in range(M):
r, c, s, d, z = map(int, input().split())
board[r][c] = numbering
sharksInfo[numbering] = {'r': r, 'c': c, 's': s, 'd': d, 'z': z}
numbering += 1
def moveSharks():
global sharksInfo
newBoard = [[0] * (C + 1) for _ in range(R + 1)]
deleteList = []
for sharkNum in list(sharksInfo.keys()):
shark = sharksInfo[sharkNum]
r, c, s, d, z = shark['r'], shark['c'], shark['s'], shark['d'], shark['z']
if d == 1 or d == 2:
cycle = (R * 2) - 2
else:
cycle = (C * 2) - 2
s = s % cycle
x, y, direction = r, c, d
for _ in range(s):
nx = x + dx[direction]
ny = y + dy[direction]
if nx < 1 or nx > R or ny < 1 or ny > C:
if direction == 1:
direction = 2
elif direction == 2:
direction = 1
elif direction == 3:
direction = 4
elif direction == 4:
direction = 3
nx = x + dx[direction]
ny = y + dy[direction]
x, y = nx, ny
if newBoard[x][y] == 0:
newBoard[x][y] = sharkNum
sharksInfo[sharkNum]['r'] = x
sharksInfo[sharkNum]['c'] = y
sharksInfo[sharkNum]['d'] = direction
else:
existingSharkNum = newBoard[x][y]
existingShark = sharksInfo[existingSharkNum]
if z > existingShark['z']:
deleteList.append(existingSharkNum)
newBoard[x][y] = sharkNum
sharksInfo[sharkNum]['r'] = x
sharksInfo[sharkNum]['c'] = y
sharksInfo[sharkNum]['d'] = direction
else:
deleteList.append(sharkNum)
for key in deleteList:
del sharksInfo[key]
return newBoard
fishKingPos = 0
answer = 0
while fishKingPos < C:
fishKingPos += 1
for i in range(1, R + 1):
if board[i][fishKingPos] > 0:
takedSharkNum = board[i][fishKingPos]
answer += sharksInfo[takedSharkNum]['z']
del sharksInfo[takedSharkNum]
board[i][fishKingPos] = 0
break
board = moveSharks()
print(answer)🎣 낚시왕 문제의 핵심: 상어 이동 최적화 비법! 🦈💨
낚시왕이 이동하면서 상어를 잡는데 상어를 잡는게 중요한게 아니다. 상어의 움직임을 나타내는것이 중요하다. 왜냐하면 일일이 이동시키면 시간초과가 발생하기 때문이다. 그렇기에 이를 최적화해야 하는데 처음부터 일일이 설명하겠다.
먼저 낚시꾼을 이동시키면서 위에서부터 탐색하면서 상어를 잡는 과정은 간단하다. 상어를 발견하면 잡아서 없애고 그대로 지우고 정답에 더해주면 되기 때문이다.
문제는 상어의 동선을 최적화해야 하는데 먼저 상어가 몇번 이동하면 제자리로 돌아오는지를 계산하면 편리하다. 즉 상어가 한바퀴 돌고 돌아오는 주기를 구해서 남은 수만큰만 이동시키면 되늗 것이다. 이는 가로와 세로에서 왕복이므로 *2를 해주고 벽때문에 줄어드는 횟수인 -2만큼 해주면 된다. 왕복 시에 벽에 두번 부딪치기 때문에 -2이다.
남은 수만큼은 그대로 진행해주면 된다. 그리고 나서 이동한 칸의 상태, 즉 빈칸인지 자신보다 큰 상어가 있는지에 따라서 나눠서 해결해주면 된다.
이렇게 Python으로 백준의 "낚시왕" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
