127. [삼성기출23]Python 백준 17143 번 낚시왕
안녕하세요 코딩하는 덕구입니다.
백준 17143 낚시왕 입니다. pypy3로 제출하지 않으면 시간초과가 뜹니다.
https://www.acmicpc.net/problem/17143
17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
www.acmicpc.net
먼저 백준 17143 번 낚시왕 코드입니다. 설명은 아래에 있습니다.
from collections import deque
import sys
input = sys.stdin.readline
R, C, M = map(int, input().split())
board = [[0 for _ in range(C)] for _ in range(R)]
tmp = []
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]
for identy in range(M):
r, c, s, d, z = map(int, input().split())
tmp.append([r-1, c-1, s, d, z, identy])
#r, c, s, d, z 위치, 속력, 방향, 크기
#d : 1위, 2아래, 3오른쪽, 4왼쪽
board[r-1][c-1] = [z, identy]
tmp.sort(key=lambda x:x[4])
sharks = deque(tmp)
def dir_change(n):
if n == 1:
return 2
elif n == 2:
return 1
elif n == 3:
return 4
elif n == 4:
return 3
def move_shark():
global board, sharks
tmp_board = [[0 for _ in range(C)] for _ in range(R)]
tmp_sharks = deque()
while sharks:
r, c, s, d, z, identy = sharks.pop()
cnt = 0
while cnt < s:
nr = dx[d] + r
nc = dy[d] + c
if 0 > nr or nr >= R or nc < 0 or nc >= C:
d = dir_change(d)
continue
r = nr
c = nc
cnt += 1
if tmp_board[r][c] == 0:
tmp_board[r][c] = [z, identy]
tmp_sharks.appendleft([r, c, s, d, z, identy])
board = tmp_board
sharks = tmp_sharks
ans = 0
for j in range(C):
for i in range(R):
if board[i][j] != 0: #낚시
size, identy = board[i][j]
board[i][j] = 0
ans += size
for shark in sharks:
if shark[5] == identy:
remove = shark
break
sharks.remove(remove)
break
move_shark()
print(ans)
문제 접근
단순한 구현 문제입니다.
상어의 움직임을 조건에 맞게 구현하고,
상어를 잡을때마다 사라지는 상어를 잘 파악하면 됩니다.
Python 코드 구현
먼저 구현에 필요한 변수들을 선언합니다.
from collections import deque
import sys
input = sys.stdin.readline
R, C, M = map(int, input().split())
board = [[0 for _ in range(C)] for _ in range(R)]
tmp = []
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]
상어를 입력받고 deque에 저장합니다. 불필욜한 정렬을 줄이기 위해 입력받고 정렬한 후 deque에 저장합니다.
for identy in range(M):
r, c, s, d, z = map(int, input().split())
tmp.append([r-1, c-1, s, d, z, identy])
#r, c, s, d, z 위치, 속력, 방향, 크기
#d : 1위, 2아래, 3오른쪽, 4왼쪽
board[r-1][c-1] = [z, identy]
tmp.sort(key=lambda x:x[4])
sharks = deque(tmp)
for j 문 : 낚시꾼의 위치를 한칸씩 오른쪽으로 이동시킵니다.
for i 문 : 가장 가까운 곳에 상어가 있다면 상어를 잡습니다.
해당 index를 0으로 변환 시키고, duque에서 상어를 제거해줍니다.
또한 ans에 상어의 크기를 더해줍니다.
낚시가 끝나면 move_shark()를 통해 상어를 이동시킵니다.
for j in range(C):
for i in range(R):
if board[i][j] != 0: #낚시
size, identy = board[i][j]
board[i][j] = 0
ans += size
for shark in sharks:
if shark[5] == identy:
remove = shark
break
sharks.remove(remove)
break
move_shark()
상어 deque은 상어의 size를 기준으로 오름차순 정렬되어 있습니다.
따라서 가장 큰 상어 부터 나오게 되고, 이 상어가 r, c에 먼저 자리를 잡습니다.
r, c 위치에 오는 다음 상어는 더 작다는 의미이므로
잡아먹혔다고 가정하고 shark에 다시 추가할필요가 없습니다.
상어를 조건에 맞게 이동시킨 후 자리를 잡은 상어가 없다면 해당 위치에 상어를 위치시킵니다.
이후 새로운 상어 리스트에 추가합니다.
def move_shark():
global board, sharks
tmp_board = [[0 for _ in range(C)] for _ in range(R)]
tmp_sharks = deque()
while sharks:
r, c, s, d, z, identy = sharks.pop()
cnt = 0
while cnt < s:
nr = dx[d] + r
nc = dy[d] + c
if 0 > nr or nr >= R or nc < 0 or nc >= C:
d = dir_change(d)
continue
r = nr
c = nc
cnt += 1
if tmp_board[r][c] == 0:
tmp_board[r][c] = [z, identy]
tmp_sharks.appendleft([r, c, s, d, z, identy])
board = tmp_board
sharks = tmp_sharks
아래의 코드는 상어가 벽을 만나게 되면 상어의 방향을 바꿔주는 코드입니다.
def dir_change(n):
if n == 1:
return 2
elif n == 2:
return 1
elif n == 3:
return 4
elif n == 4:
return 3
파이썬 백준 17143 번 낚시왕 최종 코드입니다.
from collections import deque
import sys
input = sys.stdin.readline
R, C, M = map(int, input().split())
board = [[0 for _ in range(C)] for _ in range(R)]
tmp = []
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]
for identy in range(M):
r, c, s, d, z = map(int, input().split())
tmp.append([r-1, c-1, s, d, z, identy])
#r, c, s, d, z 위치, 속력, 방향, 크기
#d : 1위, 2아래, 3오른쪽, 4왼쪽
board[r-1][c-1] = [z, identy]
tmp.sort(key=lambda x:x[4])
sharks = deque(tmp)
def dir_change(n):
if n == 1:
return 2
elif n == 2:
return 1
elif n == 3:
return 4
elif n == 4:
return 3
def move_shark():
global board, sharks
tmp_board = [[0 for _ in range(C)] for _ in range(R)]
tmp_sharks = deque()
while sharks:
r, c, s, d, z, identy = sharks.pop()
cnt = 0
while cnt < s:
nr = dx[d] + r
nc = dy[d] + c
if 0 > nr or nr >= R or nc < 0 or nc >= C:
d = dir_change(d)
continue
r = nr
c = nc
cnt += 1
if tmp_board[r][c] == 0:
tmp_board[r][c] = [z, identy]
tmp_sharks.appendleft([r, c, s, d, z, identy])
board = tmp_board
sharks = tmp_sharks
ans = 0
for j in range(C):
for i in range(R):
if board[i][j] != 0: #낚시
size, identy = board[i][j]
board[i][j] = 0
ans += size
for shark in sharks:
if shark[5] == identy:
remove = shark
break
sharks.remove(remove)
break
move_shark()
print(ans)
백준 17143 번 낚시왕 Python 코드였습니다.
감사합니다.