import sys
def input():
return sys.stdin.readline().rstrip()
def fishing(y):
for x in sorted(shark_dict[y].keys()):
if shark_dict[y][x]:
temp = shark_dict[y][x][2]
del shark_dict[y][x]
return temp
return 0
R,C,M = map(int,input().split())
shark_dict = [{} for _ in range(C)]
for _ in range(M):
x,y,speed,dire,size = map(int,input().split())
x -= 1
y -= 1
dire -= 1
shark_dict[y][x] = [dire,speed,size]
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
remain_cnt = 0
move_shark_dict = [{} for _ in range(C)]
result += fishing(y)
for shark_y in range(C):
for shark_x in shark_dict[shark_y]:
dire, speed, size = shark_dict[shark_y][shark_x]
nx = shark_x
ny = shark_y
if dire in [0,1]:
for _ in range(speed):
nx += dx[dire]
if nx >= R-1 or nx <= 0:
dire = reverse[dire]
if nx >= R:
nx = R - 2
elif nx<0:
nx = 1
else:
for _ in range(speed):
ny += dy[dire]
if ny >= C-1 or ny <= 0:
dire = reverse[dire]
if ny >=C:
ny = C-2
elif ny<0:
ny = 1
if move_shark_dict[ny].get(nx):
if move_shark_dict[ny][nx][2] < size:
move_shark_dict[ny][nx] = [dire, speed, size]
else:
move_shark_dict[ny][nx] = [dire,speed,size]
remain_cnt += 1
if remain_cnt:
shark_dict = [{} for _ in range(C)]
for y in range(C):
for x in move_shark_dict[y]:
shark_dict[y][x] = move_shark_dict[y][x]
else:
break
print(result)
문제에서 정해준대로 구현과 시뮬레이션을 정직하게 한 방법이다.
즉 이동도 한칸 한칸씩 이동을 해서 통과는 했지만 시간은 오래 걸리는 풀이 방법이다.
import sys
def input():
return sys.stdin.readline().rstrip()
def fishing(y):
for x in sorted(shark_dict[y].keys()):
if shark_dict[y][x]:
temp = shark_dict[y][x][2]
del shark_dict[y][x]
return temp
return 0
R,C,M = map(int,input().split())
shark_dict = [{} for _ in range(C)]
for _ in range(M):
x,y,speed,dire,size = map(int,input().split())
x -= 1
y -= 1
dire -= 1
shark_dict[y][x] = [dire,speed,size]
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
remain_cnt = 0
move_shark_dict = [{} for _ in range(C)]
result += fishing(y)
for shark_y in range(C):
for shark_x in shark_dict[shark_y]:
dire, speed, size = shark_dict[shark_y][shark_x]
nx = shark_x + dx[dire]*speed
ny = shark_y + dy[dire]*speed
if dire in [0,1]:
while not(0<=nx<R):
if nx<0:
nx = -nx
dire = reverse[dire]
else:
nx = (R-1)-(nx-(R-1))
dire = reverse[dire]
else:
while not(0<=ny<C):
if ny<0:
ny = -ny
dire = reverse[dire]
else:
ny = (C-1)-(ny-(C-1))
dire = reverse[dire]
if move_shark_dict[ny].get(nx):
if move_shark_dict[ny][nx][2] < size:
move_shark_dict[ny][nx] = [dire, speed, size]
else:
move_shark_dict[ny][nx] = [dire,speed,size]
remain_cnt += 1
if remain_cnt:
shark_dict = [{} for _ in range(C)]
for y in range(C):
for x in move_shark_dict[y]:
shark_dict[y][x] = move_shark_dict[y][x]
else:
break
print(result)
두번째 풀이는 방향을 한번에 구하는 것을 통해 시간을 아낄수 있었다. 정확히 말하면 한번은 아니지만, 한칸한칸씩 움직이는 것보다 빠르게 만들었다.
import sys
def input():
return sys.stdin.readline().rstrip()
def fishing(y):
for x in range(R):
if pos[x][y]:
size = sharks[pos[x][y]][4]
del sharks[pos[x][y]]
pos[x][y] = 0
return size
return 0
R,C,M = map(int,input().split())
sharks = {}
pos = [[0 for _ in range(C)] for _ in range(R)]
for num in range(1,M+1):
x,y,speed,dire,size = map(int,input().split())
x -= 1
y -= 1
dire -= 1
sharks[num] = (x,y,speed,dire,size)
pos[x][y] = num
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
if len(sharks)==0:
break
result += fishing(y)
next_pos = [[0 for _ in range(C)] for _ in range(R)]
eaten = []
for num in sharks:
shark_x,shark_y,speed,dire,size = sharks[num]
nx = shark_x + dx[dire]*speed
ny = shark_y + dy[dire]*speed
if dire in [0,1]:
while not(0<=nx<R):
if nx<0:
nx = -nx
dire = reverse[dire]
else:
nx = (R-1)-(nx-(R-1))
dire = reverse[dire]
else:
while not(0<=ny<C):
if ny<0:
ny = -ny
dire = reverse[dire]
else:
ny = (C-1)-(ny-(C-1))
dire = reverse[dire]
if next_pos[nx][ny] != 0:
prev_shark_num = next_pos[nx][ny]
if sharks[prev_shark_num][4] < size:
next_pos[nx][ny] = num
sharks[num] = (nx,ny,speed,dire,size)
eaten.append(prev_shark_num)
else:
eaten.append(num)
else:
next_pos[nx][ny] = num
sharks[num] = (nx,ny,speed,dire,size)
for num in eaten:
del sharks[num]
pos = [row[:] for row in next_pos]
print(result)
이 풀이는 상어의 정보를 저장하는 딕셔너리와 상어의 위치를 알 수 있는 리스트를 통해 관리를 해서 푸는 방식이다.