127. [삼성기출23]Python 백준 17143 번 낚시왕

안녕하세요 코딩하는 덕구입니다.

백준 17143 낚시왕 입니다. pypy3로 제출하지 않으면 시간초과가 뜹니다.

https://www.acmicpc.net/problem/17143

17143번: 낚시왕

 

먼저 백준 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 코드였습니다.

감사합니다.