[백준 17143] 낚시왕

문제 보기

이 문제는 시뮬레이션 문제이다.

생각보다 쉬워보였는데 문제를 해결하는데 하루 2시간씩 총 3일이 걸렸다. (정말 바보같았다.)

처음에는 객체지향적으로 상어 클래스를 만들고 상어들의 배열을 만들어서 선형적인 시간복잡도로 문제를 해결하려고 했지만, 딱히 그럴 필요가 없을 것 같아서 그냥 2차원 배열의 각 원소들에게 상어의 정보를 할당하였다.

문제를 푼 로직은 다음과 같다.

 

1. 2차원 배열에 상어에 대한 정보를 저장한다. (30~33번째 줄)
2. 어부를 이동시킨다. (38~39번째 줄)
3. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다. (40~45번째 줄)
4. 상어가 이동한다. (각 상어가 이동할 때마다 이동한 상어의 정보를 새로운 2차원 배열에 저장한다.) (47~58번째 줄)
5. 새로운 2차원 배열을 기준으로 2번~4번 작업을 반복해서 실행한다. (59번째 줄)

 

위 로직중 내가 실수했던 부분이자, 가장 신경써야 할 부분은 상어를 이동시키는 부분이다.

상어를 이동시킬 때, 최대 이동속도가 1000이므로 이를 최소화하고자 하였다. (6~10번째 줄)

결론적으로 상어가 벽에 부딪혀 원래의 위치로 돌아오기까지는 속도 % (2 * 벽의 길이) - 2로 계산해야 했지만, 나는 속도 % (2 * 벽의 길이) - 1로 계산을 했었다.

이 문제를 해결하는데 시간이 오래 걸렸던 이유는, 테스트케이스는 물론 질문게시판에 있는 모든 반례가 다 통과되었기 때문에 어느 부분이 문제였는지 애초부터 몰랐던 것이다.

다음부터는 모듈러 연산을 사용할 때 조금 더 주의깊게 살펴봐야겠다.

 

import sys
 
 
def move(r, c, s, d, z):
    temp_speed = s
    # minimize the steps of shark's movement
    if d == 1 or d == 2:
        temp_speed %= (2 * R) - 2
    elif d == 3 or d == 4:
        temp_speed %= (2 * C) - 2
    
    new_r, new_c, new_d = r, c, d
    for _ in range(temp_speed):
        if new_d == 1 and new_r == 1:
            new_d = 2
        elif new_d == 2 and new_r == R:
            new_d = 1
        elif new_d == 3 and new_c == C:
            new_d = 4
        elif new_d == 4 and new_c == 1:
            new_d = 3
        
        new_r += directions[new_d][0]
        new_c += directions[new_d][1]
    
    return new_r, new_c, s, new_d, z
 
 
R, C, M = map(int, sys.stdin.readline().split())
board = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
for _ in range(M):
    r, c, s, d, z = map(int, sys.stdin.readline().split())
    board[r][c] = [s, d, z]
directions = {1: (-1, 0), 2: (1, 0), 3: (0, 1), 4: (0, -1)}
 
 
answer = 0
# 1. move fisher
for fisher_pos in range(1, C + 1, 1):
    # 2. get the nearest shark from the ground
    for r in range(1, R + 1, 1):
        if board[r][fisher_pos]:
            answer += board[r][fisher_pos][2]
            board[r][fisher_pos] = 0
            break
 
    # 3. move sharks
    temp_board = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
    for r in range(1, R + 1, 1):
        for c in range(1, C + 1, 1):
            if board[r][c]:
                new_r, new_c, s, d, z = move(r, c, board[r][c][0], board[r][c][1], board[r][c][2])
                
                # if sharks conflict
                if temp_board[new_r][new_c] == 0:
                    temp_board[new_r][new_c] = [s, d, z]
                elif z > temp_board[new_r][new_c][2]:
                    temp_board[new_r][new_c] = [s, d, z]
    board = temp_board
print(answer)