낚시왕
문제링크
https://www.acmicpc.net/problem/17143
코드
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from copy import deepcopy
import sys
sys.stdin = open("input.txt",'r')
R, C, M = map(int,input().split())
board = [[0]*C for _ in range(R)]
for _ in range(M):
r,c,s,d,z = map(int,input().split())
board[r-1][c-1] = [s,d,z] #속력, 이동방향, 크기
dir = [[-1,0],[1,0],[0,1],[0,-1]]
# 낚시왕이 오른쪽으로 한 칸 이동한다.
# 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
# 상어가 이동한다.
ans = 0
def outrange(i,j,fast,d):
dx, dy = dir[d-1]
if d == 1 or d == 2:
fast = fast % ((R-1)*2)
elif d == 3 or d == 4:
fast = fast % ((C-1)*2)
while True:
if -1 < i+dx*fast < R and -1 < j+dy*fast < C:
return (i+dx*fast, j+dy*fast, d)
if d == 1:
fast -= i # 가장 위로 만들어주고
dx, dy = 1, 0 # 방향 바꿔버리기
i = 0
d = 2
elif d == 2: # 가장 아래로 만들어주고
fast -= (R-1-i)
dx, dy = -1, 0
i = R-1
d = 1
elif d == 3: # 가장 오른쪽으로 만들고
fast -= (C-1-j)
dx, dy = 0, -1
j = C -1
d = 4
elif d == 4: # 가장 왼쪽
fast -= j
dx, dy = 0, 1
j = 0
d = 3
# 상어를 잡는 낚시꾼
for j in range(C):
for i in range(R):
if board[i][j] != 0:
ans += board[i][j][2]
board[i][j] = 0
break
# 상어의 이동
new_board= [[0]*C for _ in range(R)]
for i in range(R):
for j in range(C):
if board[i][j] != 0: # 상어가 있다면
fast = board[i][j][0]
nx, ny, d = outrange(i,j,fast,board[i][j][1])
if new_board[nx][ny] == 0: # 아무도 없을때
new_board[nx][ny] = [board[i][j][0],d,board[i][j][2]]
else: # 있다면 잡아먹으렴...
if new_board[nx][ny][2] < board[i][j][2]:
new_board[nx][ny] = [board[i][j][0],d,board[i][j][2]]
board = deepcopy(new_board)
print(ans)
풀이
먼저 상어의 정보를 나타내는 board 배열을 초기화하였고, input 받는 값으로 상어가 위치한 자리에는 [속력, 이동방향, 크기 로 나타내었다.
먼저 문제에서 주어진 조건대로, 낚시꾼을 0의 열에서 시작해서 그 자리에서 위치한 가장 가까운 상어를 잡았다.
그리고 상어를 잡은 후 # 상어의 이동을 시작한다. 이동을할때 주의해야할 점은 두가지인데
- 새로 이동한자리에 상어가 있을 경우
- 상어가 이동하다가 경계선을 만날 경우
이다.
먼저 첫번째의 상황 새로 이동한 자리에 상어가 있을 경우를 판별하기 위해 new_board 값을 만들어 주었다. 그리고 차례차례 board를 돌면서 해당 위치에 상어가 있을 경우 해당 상어의 정보에 따라 최종 이동한자리에 아무도 없을 경우 새로운 자리로 할당해 주었다. 여기서 최종 자리에 상어가 있는지 없는지의 유무는 new_board가 0 인지 아닌지를 분석한뒤 판단해주었다. 그런데 문제는 두번째 상황인 상어가 이동하다가 경계선을 만날 경우 이다. 이 경우에는 outrange 함수를 만들어서 최종이동 자리와 최종 바뀌어진 혹은 그대로인 방향값을 반환해 주었다. (i+dx*fast, j+dy*fast, d)
그럼 이제, outrange 함수를 살펴보자.
먼저 속력의 값때문에 몇바퀴를 돌아도 제자리인 경우가 있으므로 시간초과를 방지하기 위해
1
2
3
4
if d == 1 or d == 2:
fast = fast % ((R-1)*2)
elif d == 3 or d == 4:
fast = fast % ((C-1)*2)
로 fast 즉 속력 값을 초기화해주었다. 어차피 상수값이라 반환시에 값이 변하지 않으므로 동일한 변수인 fast에 할당해주었다.
그리고 이제, 최종자리를 찾는 알고리즘인데 해당 알고리즘은 다음과 같다.
- 만약 범위가 넘어간다면, 현재의 자리에서 경계자리까지 이동하는데 필요한 칸수를
fast에서 빼준다. - 그리고 현재의 위치를 경계자리로 옮겨준다.
- 또 방향도 반대 방향으로 바꿔준다.
이것을 방향에 따라 경우를 나누어 아래와 같은 방식으로 구현하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if d == 1:
fast -= i # 가장 위로 만들어주고
dx, dy = 1, 0 # 방향 바꿔버리기
i = 0
d = 2
elif d == 2: # 가장 아래로 만들어주고
fast -= (R-1-i)
dx, dy = -1, 0
i = R-1
d = 1
elif d == 3: # 가장 오른쪽으로 만들고
fast -= (C-1-j)
dx, dy = 0, -1
j = C -1
d = 4
elif d == 4: # 가장 왼쪽
fast -= j
dx, dy = 0, 1
j = 0
d = 3
그리고 반환된 값에 new_board에 해당 값을 할당해준다. 이렇게 모두 이동을 마친뒤에는 board 값에 deepcopy 모듈을 사용하여 값을 복사해준다.