728x90
문제 설명
낚시왕은 크기가 R×C인 격자판에서 상어 낚시를 한다. 격자판의 각 칸에는 상어가 있을 수 있으며, 상어는 위치 (r,c), 속력 s, 이동 방향 d, 크기 를 가진다.
낚시왕은 첫 번째 열의 왼쪽에 위치하며, 매 초마다 오른쪽으로 한 칸씩 이동한다. 매 시간마다 다음과 같은 일이 발생한다:
- 낚시왕이 이동한다.
- 낚시왕이 있는 열에서 가장 가까운 상어를 잡는다. 잡은 상어는 격자판에서 사라진다.
- 상어들이 이동한다. 각 상어는 자신의 속력과 방향에 따라 이동하며, 격자판의 경계를 넘으면 방향을 반대로 바꾸며 이동을 계속한다.
- 같은 칸에 여러 상어가 있다면 크기가 가장 큰 상어만 남고 나머지는 모두 사라진다.
낚시왕이 잡은 상어 크기의 합을 구하는 것이 목표이다.
입력 조건
- 첫째 줄에 격자판의 크기 R,C와 상어의 수 M이 주어진다. (2≤R,C≤100, 0≤M≤R×C)
- 다음 M개의 줄에는 상어의 정보가 주어진다.
- r,c,s,d,z: 상어의 위치 (r,c), 속력 s, 이동 방향 d, 크기 z
- 방향 d: 1(위), 2(아래), 3(오른쪽), 4(왼쪽)
문제 접근
이 문제는 시뮬레이션 문제로, 시간의 흐름에 따라 상태를 정확하게 업데이트해야 한다. 주요 고려 사항은 다음과 같다:
- 낚시왕의 이동 및 상어 낚시: 낚시왕은 매 시간마다 오른쪽으로 한 칸씩 이동하며, 현재 열에서 가장 가까운 상어를 잡는다.
- 상어의 이동: 각 상어는 자신의 속력과 방향에 따라 이동한다. 이동 중에 경계를 넘으면 방향을 반대로 바꾸며 이동한다.
- 상어의 겹침 처리: 이동 후 같은 칸에 여러 상어가 있다면 크기가 가장 큰 상어만 남긴다.
해결 방법
1. 데이터 구조 정의
- 상어의 위치와 정보를 저장하기 위해 딕셔너리를 사용한다.
- 키: 상어의 위치 (x,y)
- 값: [s,d,z](속력, 방향, 크기)
2. 방향 설정
- 방향은 다음과 같이 설정한다:
- 0: 위 (−1,0)
- 1: 아래 (1,0)
- 2: 오른쪽 (0,1)
- 3: 왼쪽 (0,−1)
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
3. 상어 이동 함수 구현
상어의 이동을 반복문 없이 수학적으로 계산한다.
- 상어의 이동 주기(cycle)를 계산한다.
- 세로 이동 주기: cycle=2×(R−1)
- 가로 이동 주기: cycle=2×(C−1)
- 속력을 주기로 나눈 나머지를 사용하여 실제 이동 거리를 계산한다.
- 경계를 넘으면 대칭 위치로 이동하고, 방향을 반대로 바꾼다.
def move_shark(x, y, s, d):
if d == 0 or d == 1: # 위 또는 아래
cycle = 2 * (R - 1)
s %= cycle
for _ in range(s):
x += dx[d]
if x < 0 or x >= R:
d = 1 - d
x += 2 * dx[d]
else: # 오른쪽 또는 왼쪽
cycle = 2 * (C - 1)
s %= cycle
for _ in range(s):
y += dy[d]
if y < 0 or y >= C:
d = 5 - d
y += 2 * dy[d]
return x, y, d
하지만 위의 함수에서도 반복문이 사용되므로, 반복문을 제거하여 최적화한다.
def move_shark(x, y, s, d):
if d == 0 or d == 1: # 세로 이동
cycle = 2 * (R - 1)
s %= cycle
if d == 0:
x -= s
if x < 0:
x = -x
d = 1
if x >= R:
x = cycle - x
d = 0
else:
x += s
if x >= R:
x = cycle - x
d = 0
if x < 0:
x = -x
d = 1
else: # 가로 이동
cycle = 2 * (C - 1)
s %= cycle
if d == 2:
y += s
if y >= C:
y = cycle - y
d = 3
if y < 0:
y = -y
d = 2
else:
y -= s
if y < 0:
y = -y
d = 2
if y >= C:
y = cycle - y
d = 3
return x, y, d
4. 시뮬레이션 진행
- 낚시왕은 왼쪽에서 시작하여 오른쪽으로 한 칸씩 이동한다.
- 각 열에서 가장 가까운 상어를 잡고, 잡은 상어의 크기를 누적한다.
- 상어들을 이동시키고, 이동 후 같은 위치에 있는 상어들은 크기를 비교하여 하나만 남긴다.
백준 17143 낚시왕 파이썬 정답 코드
import sys
input = sys.stdin.readline
R, C, M = map(int, input().split())
sharks = dict()
for _ in range(M):
r, c, s, d, z = map(int, input().split())
sharks[(r - 1, c - 1)] = [s, d - 1, z]
dx = [-1, 1, 0, 0] # 위, 아래, 오른쪽, 왼쪽
dy = [0, 0, 1, -1]
def move_shark(x, y, s, d):
if d == 0 or d == 1: # 세로 이동
cycle = 2 * (R - 1)
if cycle != 0:
s %= cycle
if d == 0:
x -= s
if x < 0:
x = -x
d = 1
if x >= R:
x = cycle - x
d = 0
else:
x += s
if x >= R:
x = cycle - x
d = 0
if x < 0:
x = -x
d = 1
else: # 가로 이동
cycle = 2 * (C - 1)
if cycle != 0:
s %= cycle
if d == 2:
y += s
if y >= C:
y = cycle - y
d = 3
if y < 0:
y = -y
d = 2
else:
y -= s
if y < 0:
y = -y
d = 2
if y >= C:
y = cycle - y
d = 3
return x, y, d
total_catch = 0
for col in range(C):
# 낚시왕이 있는 열에서 가장 가까운 상어 잡기
min_row = R
shark_pos = None
for row in range(R):
if (row, col) in sharks:
if row < min_row:
min_row = row
shark_pos = (row, col)
if shark_pos:
total_catch += sharks[shark_pos][2]
del sharks[shark_pos]
# 상어 이동
new_sharks = dict()
for (x, y), (s, d, z) in sharks.items():
nx, ny, nd = move_shark(x, y, s, d)
if (nx, ny) in new_sharks:
if new_sharks[(nx, ny)][2] < z:
new_sharks[(nx, ny)] = [s, nd, z]
else:
new_sharks[(nx, ny)] = [s, nd, z]
sharks = new_sharks
print(total_catch)
결론
이 문제는 시뮬레이션과 구현 능력을 요구하는 문제로, 각 단계에서 발생하는 상태 변화를 정확히 추적해야 한다. 특히, 상어의 이동에서 반복문을 제거하고 수학적인 계산으로 이동을 처리하여 시간 복잡도를 최적화해야 한다.
도움이 되셨다면 공감과 댓글 부탁드립니다.
728x90
'Python > 백준' 카테고리의 다른 글
백준 연구소 3 [17142] 파이썬(Python) 코드 + 해설 (1) | 2024.11.06 |
---|---|
백준 이차원 배열과 연산 [17140] 파이썬(Python) 코드 + 해설 (0) | 2024.11.05 |
백준 미세먼지 안녕! [17144] 파이썬(Python) 코드 + 해설 (0) | 2024.11.03 |
백준 아기 상어 [16326] 파이썬(Python) 코드 + 해설 (1) | 2024.11.02 |
백준 나무 재테크 [16325] 파이썬(Python) 코드 + 해설 (2) | 2024.11.02 |