https://www.acmicpc.net/problem/17143
접근
이번 문제에는 상어들의 step 크기가 최대 1000이다. 따라서 최대 RxC 마리의 상어들의 모두 1000의 크기만큼 이동할 때 한 칸씩 이동하도록 구현하면 시간초과가 발생한다. 따라서 상어들의 step 크기를 줄여야했다.
이를 위해 규칙을 찾아보면 상하로 움직이는 상어들은 (R-1) x 2배, 좌우로 움직이는 상어들은 (C - 1) x 2배일 때 같은 자리로 돌아오게 된다. 따라서 위의 연산으로 나눈 나머지로 step을 설정한다면 이동 횟수를 줄일 수 있다.
구현
- 상어들의 정보를 입력받는다.
- 방향이 상하라면 s를 (R - 1) x 2로 나눈 나머지로 변환하고 좌우라면 (C - 1) x 2로 나눈 나머지로 변환한다.
- 이후 r, c 위치에 s, d, z를 저장한다.
R, C, M = map(int, input().split())
board = [[[] for _ in range(C)] for _ in range(R)]
dy = [-1, 1, 0, 0]
dx = [0, 0, 1, -1]
for _ in range(M):
r, c, s, d, z = map(int, input().split())
r -= 1
c -= 1
d -= 1
if d == 0 or d == 1:
s %= ((R - 1) * 2)
else:
s %= ((C - 1) * 2)
board[r][c] = [s, d, z]
- 낚시왕이 오른쪽으로 움직이기 때문에 C만큼 for문으로 탐색한다.
- 이제 각각의 위치를 find_shark 함수로 전달하여 가장 가까운 상어를 찾아 answer에 저장한다.
- 이후 move_shark에 상어들의 정보가 저장된 2차원 리스트인 board를 전달하여 상어를 이동시킨 새로운 board를 전달받는다.
for i in range(C):
answer += find_shark(i)
board = move_shark(board)
- 상어들이 이동한 결과를 담을 새로운 2차원 리스트인 new_board를 생성한다.
- 기존의 board를 탐색하여 상어가 존재하는 곳일 때 상어를 이동시킨다.
- s만큼 이동시키다가 맵을 벗어났을 때 방향을 변환하여 이동한다.
- 상어가 새로운 위치에 도착했을 때 이미 상어가 있다면 크기를 비교하여 변경하고 아니라면 해당 위치에 상어의 정보를 저장한다.
- 최종적으로 new_board를 반환한다.
def move_shark(board):
new_board = [[[] for _ in range(C)] for _ in range(R)]
for y in range(R):
for x in range(C):
if board[y][x] and board[y][x][0] != -1:
s, d, z = board[y][x][0], board[y][x][1], board[y][x][2]
ny, nx = y, x
step = s
while step:
ny += dy[d]
nx += dx[d]
if not check_range(ny, nx):
ny -= dy[d]
nx -= dx[d]
d = change_direction(d)
ny += dy[d]
nx += dx[d]
step -= 1
if new_board[ny][nx]:
if new_board[ny][nx][2] < z:
new_board[ny][nx] = [s, d, z]
else:
new_board[ny][nx] = [s, d, z]
return new_board
전체 코드
import sys
input = sys.stdin.readline
def check_range(y, x):
return (0 <= y < R) and (0 <= x < C)
def find_shark(col):
for y in range(R):
if board[y][col]:
board[y][col][0] = -1
return board[y][col][2]
return 0
def change_direction(d):
if d == 0:
return 1
elif d == 1:
return 0
elif d == 2:
return 3
else:
return 2
def move_shark(board):
new_board = [[[] for _ in range(C)] for _ in range(R)]
for y in range(R):
for x in range(C):
if board[y][x] and board[y][x][0] != -1:
s, d, z = board[y][x][0], board[y][x][1], board[y][x][2]
ny, nx = y, x
step = s
while step:
ny += dy[d]
nx += dx[d]
if not check_range(ny, nx):
ny -= dy[d]
nx -= dx[d]
d = change_direction(d)
ny += dy[d]
nx += dx[d]
step -= 1
if new_board[ny][nx]:
if new_board[ny][nx][2] < z:
new_board[ny][nx] = [s, d, z]
else:
new_board[ny][nx] = [s, d, z]
return new_board
R, C, M = map(int, input().split())
board = [[[] for _ in range(C)] for _ in range(R)]
dy = [-1, 1, 0, 0]
dx = [0, 0, 1, -1]
for _ in range(M):
r, c, s, d, z = map(int, input().split())
r -= 1
c -= 1
d -= 1
if d == 0 or d == 1:
s %= ((R - 1) * 2)
else:
s %= ((C - 1) * 2)
board[r][c] = [s, d, z]
answer = 0
for i in range(C):
answer += find_shark(i)
board = move_shark(board)
print(answer)
'알고리즘 풀이 > 백준' 카테고리의 다른 글
[백준 17825] 주사위 윷놀이 (0) | 2021.10.13 |
---|---|
[백준 20040] 사이클 게임 (0) | 2021.10.06 |
[백준 20058] 마법사 상어와 파이어스톰 (0) | 2021.09.23 |
[백준 20922] 겹치는 건 싫어 (0) | 2021.09.08 |
[백준 14003] 가장 긴 증가하는 부분 수열 5 (0) | 2021.09.02 |