17143. 낚시왕 문제 바로가기
해결 방법
문제에서 제시된 1초동안 일어나는 과정
낚시왕이 오른쪽으로 한 칸 이동한다.코드 13번째 줄 for 문을 통해 이동할 수있도록 구현했다.
낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.낚시왕이 있는 위치(m) 기준으로 열을 탐색하여 0 이 아닌 경우
- catch_shark_sum에 상어 크기 더하기
- 잡은 상어 ocean에서 0으로 만들어 제거하기
- break를 통해 제일 가까운 상어를 잡을 수 있도록 종료시키기
상어가 이동한다.★상어가 이동하면 그 결과를 n_ocean 이라는 새로운 이중 리스트에 저장했다.
이때 가장 주의할 점!!!
격자판의 경계를 넘는 경우 방향을 바꾸고 이동하기
움직일 때마다 경계값인지 if 문을 통해 확인하고 경계에 있으면 방향을 바꿔준다.
s를 통해 이동 거리를 하나씩 움직여준다면 시간 초과를 볼 수 있다. 따라서 상어가 이동할 때 자기 자리로 돌아오는 불필요한 이동을 줄이기 위해
- 위, 아래 방향인 경우 : s % ((R - 1) * 2)
- 왼쪽, 오른쪽 방향인 경우: s % ((C - 1) * 2)
다음 계산을 진행했다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# 상어 이동할 자리를 찾는 주요 코드 if ocean[y][x] != 0: # 상어가 있으면 s, d, z = ocean[y][x] ny, nx = y, x if d in [0, 1]: # 위, 아래 방향으로 움직인는 경우 move = s % ((R - 1) * 2) # 시간 초과 방지 (한 바퀴 돌아 제자리 불필요한 계산 제거) while move: if ny == 0: d = 1 # 경계 넘는 경우 방향 바꾸기 if ny == R - 1: d = 0 ny += dirs[d][0] move -= 1 else: # 왼쪽, 오른쪽 방향으로 움직인는 경우 move = s % ((C - 1) * 2) # 시간 초과 방지 (한 바퀴 돌아 제자리 불필요한 계산 제거) while move: if nx == 0: d = 2 # 경계 넘는 경우 방향 바꾸기 if nx == C - 1: d = 3 nx += dirs[d][1] move -= 1
이후 상어의 이동할 위치를 찾았다면 n_ocean에 저장하기
0이 아닌 경우 (상어가 있는 경우)
상어의 크기 비교를 통해 큰 상어만 남을 수 있도록 한다.
구현한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from copy import deepcopy
R, C, M = map(int, input().split())
ocean = [[0] * C for _ in range(R)] # 상어 정보([s, d, z]) 저장한 이중 리스트
for _ in range(M):
r, c, s, d, z = map(int, input().split())
ocean[r - 1][c - 1] = [s, d - 1, z]
dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
catch_shark_sum = 0
for m in range(C): # 1. 낚시왕이 오른쪽으로 한 칸 이동한다.
for r in range(R): # 2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
if ocean[r][m] != 0:
catch_shark_sum += ocean[r][m][2]
ocean[r][m] = 0 # 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
break
# 3. 상어가 이동한다.
n_ocean = [[0] * C for _ in range(R)] # 이동한 상어를 저장할 리스트
for y in range(R):
for x in range(C):
if ocean[y][x] != 0: # 상어가 있으면
s, d, z = ocean[y][x]
ny, nx = y, x
if d in [0, 1]: # 위, 아래 방향으로 움직인는 경우
move = s % ((R - 1) * 2) # 시간 초과 방지 (한 바퀴 돌아 제자리 불필요한 계산 제거)
while move:
if ny == 0: d = 1 # 경계 넘는 경우 방향 바꾸기
if ny == R - 1: d = 0
ny += dirs[d][0]
move -= 1
else: # 왼쪽, 오른쪽 방향으로 움직인는 경우
move = s % ((C - 1) * 2) # 시간 초과 방지 (한 바퀴 돌아 제자리 불필요한 계산 제거)
while move:
if nx == 0: d = 2 # 경계 넘는 경우 방향 바꾸기
if nx == C - 1: d = 3
nx += dirs[d][1]
move -= 1
if n_ocean[ny][nx] == 0:
n_ocean[ny][nx] = [s, d, z]
# 이동하려는 곳에 상어가 있다면 크기가 큰 상어만 남기기
elif n_ocean[ny][nx][2] < z:
n_ocean[ny][nx] = [s, d, z]
ocean = deepcopy(n_ocean)
print(catch_shark_sum)
###