문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 보러 가기
접근 과정
가볍게 생각하고 접근했지만, 생각보다 신경 쓸 부분이 많았던 문제였다.
낚시왕은 1번 열의 한 칸 왼쪽에서 오른쪽으로 한 칸씩 이동하기 때문에, 낚시왕이 위치한 열에서 가장 가까운 상어를 잡고, 상어들이 각자의 속력과 방향에 따라 이동하는 과정은 총 C회 이루어진다.
이 조건으로만 생각하면, 단순히 2차원 배열에 상어의 정보를 넣고 C회 반복되는 루프 안에서 낚시왕이 열을 옮겨다니며 상어를 낚는 과정, 상어가 이동하는 과정을 구현하기만 하면 끝나겠지만 이 조건으로만 충실히 구현하면 시간 초과나, 인덱스 에러가 발생한다.
생각해봐야 할 부분은 아래와 같다!
-
상어는 생각보다 많이 움직인다
상어의 이동 횟수 s는 최대 1000이다. 최악의 경우로 계산했을 때, R x C 크기의 2차원 배열에 존재할 수 있는 상어의 최대 수는 R x C 마리이다! R x C마리의 상어들이 1000회씩 움직이는 과정들이 C회(낚시왕은 C회만큼 움직이기 때문)만큼 반복되는데, 이 과정을 전부 구현하면 시간 초과가 발생한다.
6 x 6 사이즈의 2차원 배열 내 (4, 4)좌표에 상어가 한 마리 있고, 왼쪽 방향으로 움직인다고 가정해보자. 상어의 이동 횟수가 1000이라고 가정했을 때, 1000회의 이동을 전부 구현해야 할까?
상어는 정해진 속도로(한 칸씩), 정해진 방향으로(가장자리에 닿으면 반대 방향으로) 일정하게 이동한다. 그 말은, 상어가 이동하다 보면, 특정 횟수마다 시작한 위치로 다시 돌아올 수 있다는 것을 의미한다!
상어가 6 x 6 사이즈의 2차원 배열에서 (4,4) 좌표를 시작점으로, 왼쪽으로 이동한다고 가정했을 때, 상어는 총 10회의 이동을 통해 시작점으로 다시 돌아올 수 있다.
이를 다시 다듬으면, 주어진 상어의 이동 횟수 s는,s % ((가로 또는 세로 길이 - 1) * 2)로 정리해 나타낼 수 있다! 이를 통해 이동 횟수의 최적화가 가능하다. -
처음부터 가장자리인 경우를 조심하자
이렇게 시작부터 상어가 가장자리에 위치한 경우가 있을 수 있다. 처음에 상어의 이동과 이동한 좌표 값이 배열 범위 내에 있는지 검증하는 과정에서 이 부분을 생각하지 못해 어려움을 겪었다...
저렇게 상어가 유유히 탈출할 수 있다. 풀이에서는 저렇게 상어가 배열 바깥으로 탈출한 경우, 상어의 이동 방향을 반대로 바꾸고, 반대 방향으로 두칸 이동시키는 방향으로 해결하였다!
풀이
import sys
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]
def searching_shark(col):
global count
for i in range(R):
if shark_map[i][col]:
count += shark_map[i][col][0][2]
shark_map[i][col].remove(shark_map[i][col][0])
break
def moving_shark():
temp_list = [[[] for _ in range(C)] for _ in range(R)]
for i in range(R):
for j in range(C):
if shark_map[i][j]:
x, y = i, j
speed, direction, size = shark_map[i][j][0]
if direction in [1, 2]:
move_count = speed % (2 * (R - 1))
elif direction in [3, 4]:
move_count = speed % (2 * (C - 1))
for _ in range(move_count):
x, y = x + dx[direction], y + dy[direction]
if not (0 <= x < R and 0 <= y < C):
if direction % 2:
direction += 1
else:
direction -= 1
x, y = x + (dx[direction] * 2), y + (dy[direction] * 2)
temp_list[x][y].append([speed, direction, size])
for i in range(R):
for j in range(C):
shark_map[i][j] = temp_list[i][j]
input = sys.stdin.readline
R, C, M = map(int, input().split())
if not M:
print(0)
else:
shark_map = [[[] for _ in range(C)] for _ in range(R)]
count = 0
for _ in range(M):
r, c, s, d, z = map(int, input().split())
shark_map[r - 1][c - 1].append([s, d, z])
for _ in range(C):
searching_shark(_)
moving_shark()
for i in range(R):
for j in range(C):
if len(shark_map[i][j]) > 1:
shark_map[i][j].sort(key=lambda x: x[2], reverse=True)
while len(shark_map[i][j]) > 1:
shark_map[i][j].pop()
print(count)통과!
읽어주셔서 감사합니다!
