BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/17143
17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
www.acmicpc.net
내가 작성한 코드
import sys
from collections import defaultdict
_speed = 0
_direction = 1
_size = 2
def deploy_shark(sharks, r, c, speed, direction, size):
# (1) set if empty || (2) set size if the size is larger
if not sharks[c][r] or sharks[c][r][_size] < size:
sharks[c][r] = (speed, direction, size)
def read_data():
read = sys.stdin.readline
R, C, M = map(int, read().rstrip().split())
sharks = defaultdict(lambda: defaultdict(tuple))
for _ in range(M):
r, c, speed, direction, size = map(int, read().rstrip().split())
deploy_shark(sharks, r, c, speed, direction-1, size)
return R, C, M, sharks
def fishing_shark(sharks, fisher):
if sharks[fisher]:
shark = min(sharks[fisher])
size = sharks[fisher][shark][_size]
del sharks[fisher][shark]
return size
return 0
def change_direction(direction):
if direction % 2 == 1:
return direction - 1
return direction + 1
def shark_up(R, r, speed, direction):
speed = speed % ((R - 1) * 2)
if r - speed > 1:
r = r - speed
else:
direction = change_direction(direction)
r, direction = shark_down(R, 1, speed - (r - 1), direction)
return r, direction
def shark_down(R, r, speed, direction):
speed = speed % ((R - 1) * 2)
if r + speed < R:
r = r + speed
else:
direction = change_direction(direction)
r, direction = shark_up(R, R, speed - (R - r), direction)
return r, direction
def shark_left(C, c, speed, direction):
speed = speed % ((C - 1) * 2)
if c - speed > 1:
c = c - speed
else:
direction = change_direction(direction)
c, direction = shark_right(C, 1, speed - (c - 1), direction)
return c, direction
def shark_right(C, c, speed, direction):
speed = speed % ((C - 1) * 2)
if c + speed < C:
c = c + speed
else:
direction = change_direction(direction)
c, direction = shark_left(C, C, speed - (C - c), direction)
return c, direction
def shark_move(R, C, r, c, speed, direction):
# 0=up, 1=down, 2=right, 3=left
if direction == 0:
r, direction = shark_up(R, r, speed, direction)
elif direction == 1:
r, direction = shark_down(R, r, speed, direction)
elif direction == 2:
c, direction = shark_right(C, c, speed, direction)
else:
c, direction = shark_left(C, c, speed, direction)
return r, c, direction
def sharks_move(sharks, R, C):
nw_sharks = defaultdict(lambda: defaultdict(tuple))
for c, rs in sharks.items():
for r in rs:
speed, direction, size = sharks[c][r]
nw_r, nw_c, nw_direction = shark_move(R, C, r, c, speed, direction)
deploy_shark(nw_sharks, nw_r, nw_c, speed, nw_direction, size)
return nw_sharks
# main
R, C, M, sharks = read_data()
answer = 0
for fisher in range(1, C+1):
answer += fishing_shark(sharks, fisher)
sharks = sharks_move(sharks, R, C)
print(answer)
- 상어 위치
- sharks = defaultdict(lambda: defaltdict(tuple))
- sharks[c][r] = (speed, direction, size)
- 같은 위치에 상어가 있으면 size를 비교
- 상어 이동
- 제자리로 오는 경우 : speed를 speed % (R-1) * 2 or speed % (C-1) * 2로 바꿔줌
- 방향이 그대로인 경우 : r/c를 speed만큼 +/-
- 방향이 빠뀌는 경우 : (1) r/c를 가장 끝 값으로 이동 (2) direction을 바꿈 (3) 이동한만큼 뺀 speed로 반대방향 이동
다른 사람이 작성한 코드
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)
- 상어 위치를 리스트로 사용
- 최대 100 x 100으로 전체 탐색에도 문제가 없는듯
https://hoyeonkim795.github.io/posts/17143/
[백준] #17143 낚시왕 python (파이썬)
낚시왕
hoyeonkim795.github.io
기억해야할 것
- 까다로운 구현 문제
- 이런 형식의 조건이 까다로운 문제는 시간제한이 있는 경우 어려움
- 함수로 최대한 분할하여 문제를 접근하기
'코딩테스트' 카테고리의 다른 글
[백준][최대유량] 도시 왕복하기1 (0) | 2022.03.03 |
---|---|
[백준][구현] 큐빙 (0) | 2022.02.17 |
[백준][기하학] 이사 (0) | 2022.02.15 |
[백준][브루트포스] 캐슬 디펜스 (0) | 2022.02.15 |
[백준][그리디] 단어 수학 (0) | 2022.02.10 |