삼성 역량 SW 기출문제인 낚시왕 문제에 대해서 풀이과정을 작성하도록 하겠다.
문제 : https://www.acmicpc.net/problem/17143

풀이 과정

문제가 길어 복잡해보이지만 요약하면 다음과 같다.
1. 낚시왕이 있는 열에서 가장 위에 있는 상어를 잡는다.
2. 상어들이 각 상태와 속력에 맞게 움직인다.
3. 한칸에 상어가 여러마리 있다면 가장 큰 크기의 상어만 해당 칸에 존재하도록 한다.

위 과정을 모든 열(C)만큼 반복을 해주면 된다.

s를 최소화 시키자

여기서 까다로운 점은 상어의 상태와 속력을 고려하는 것이다. 문제의 조건을 살펴보면 s의 범위가 0<s<=1000임을 고려하여 while문을 통해 계속해서 값을 갱신하며 움직인다면 시간초과가 날 것이다. 따라서 각 상어의 속력과 해당 board의 크기에 맞춰서 나머지를 구하는 것이 중요하다.

예를 들어 상태가 d=1, s=20, R=8이고, 상어의 행의 위치(r)가 5라고 가정하자. (d,s,r)로 표현하면 다음과 같다.
(1,20,4)->(2,16,0)->(1,9,7)->(2,2,0)로 된다.
즉, 위에서 보는 것처럼 s %= (R-1)*2 의 형태로 나온다는 것을 알 수 있다.
이를 토대로 s를 최소화시킨 후 상어를 움직인다면 여러번의 연산 대신 한번의 연산으로 s를 구할 수 있다. 이를 토대로 코드를 작성하면 다음과 같다.

def move_sharks(cur,s,d):
    y,x = cur
    d_list = {1:(-1,0),2:(1,0),3:(0,1),4:(0,-1)}
    dy,dx = d_list[d]
    if d==1 or d==2:
        s%=(R-1)*2
    else:
        s%=(C-1)*2
    if 0<=y+dy*s<R and 0<=x+dx*s<C:
        return (y+dy*s, x+dx*s,d)
    else:
        while True:
            dy,dx = d_list[d]
            if 0<=y+dy*s<R and 0<=x+dx*s<C:
                return (y+dy*s, x+dx*s,d)
            
            if d==1:
                s-=y
                y=0
                d=2
            elif d==2:
                s-=(R-1-y)
                y=R-1
                d=1
            elif d==3:
                s-=(C-1-x)
                x=C-1
                d=4
            else:
                s-=x
                x=0
                d=3

이를 토대로 상어의 움직임을 함수로 구현하였다. 그럼 낚시왕이 낚시하는 것과 board를 갱신하는 코드를 작성하도록 하겠다.

fishing & solution

def fishing(board,c):
    for i in range(R):
        if board[i][c]:
            result = board[i][c][2]
            board[i][c]=0
            return result
    return -1
            
def solution(board):
    answer = 0
    for cur in range(C):
        fish = fishing(board,cur)
        if fish!=-1:
            answer+=fish
        temp_board = [[0] * C for _ in range(R)]
        for i in range(R):
            for j in range(C):
                if board[i][j]:
                    s,d,z = board[i][j]
                    y,x,d = move_sharks((i,j),s,d)
                    
                    if temp_board[y][x]:
                        if temp_board[y][x][2]<z:
                            temp_board[y][x]=[s,d,z]
                    else:
                        temp_board[y][x] = [s,d,z]
        board = copy.deepcopy(temp_board)
    return answer

갱신하는 board를 temp_board로 선언하고 상어가 갱신될 때마다 temp_board에 저장하자. 이 때 가장 큰 상어만 해당 칸을 차지하도록 if문을 걸어준다.
그리고 fish가 될 때만 answer값에 +를 해주자!!

전체코드

import copy

R,C,M = map(int,input().split())
board = [[0] * C for _ in range(R)]

for i in range(M):
    r,c,s,d,z = map(int,input().split())
    #r,c,s,d,z = map(int,_list[i].split())
    board[r-1][c-1]=[s,d,z]
    
def move_sharks(cur,s,d):
    y,x = cur
    d_list = {1:(-1,0),2:(1,0),3:(0,1),4:(0,-1)}
    dy,dx = d_list[d]
    if d==1 or d==2:
        s%=(R-1)*2
    else:
        s%=(C-1)*2
    if 0<=y+dy*s<R and 0<=x+dx*s<C:
        return (y+dy*s, x+dx*s,d)
    else:
        while True:
            dy,dx = d_list[d]
            if 0<=y+dy*s<R and 0<=x+dx*s<C:
                return (y+dy*s, x+dx*s,d)
            
            if d==1:
                s-=y
                y=0
                d=2
            elif d==2:
                s-=(R-1-y)
                y=R-1
                d=1
            elif d==3:
                s-=(C-1-x)
                x=C-1
                d=4
            else:
                s-=x
                x=0
                d=3
                
def fishing(board,c):
    for i in range(R):
        if board[i][c]:
            result = board[i][c][2]
            board[i][c]=0
            return result
    return -1
            
def solution(board):
    answer = 0
    for cur in range(C):
        fish = fishing(board,cur)
        if fish!=-1:
            answer+=fish
        temp_board = [[0] * C for _ in range(R)]
        for i in range(R):
            for j in range(C):
                if board[i][j]:
                    s,d,z = board[i][j]
                    y,x,d = move_sharks((i,j),s,d)
                    
                    if temp_board[y][x]:
                        if temp_board[y][x][2]<z:
                            temp_board[y][x]=[s,d,z]
                    else:
                        temp_board[y][x] = [s,d,z]
        board = copy.deepcopy(temp_board)
    return answer

print(solution(board))

Result