[Python][백준] 17143번 낚시왕

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

공부 날짜 : 2022.09.20
정답 참조 여부 : X

상어가 지속적으로 움직이고 낚시왕이 오른쪽으로 이동하며 가장 가까운 상어를 잡을 때 잡은 상어의 크기 합을 구하는 문제이다.

---

낚시왕이 상어를 낚는과정은 어렵지 않았으나 상어의 움직임이 처음보는 유형이었다.
벽을 만나면 방향이 달라지다보니 코드가 간단하다면 한칸씩 움직이며 벽인지 판단하는 방법이 있겠지만 당연히 시간초과를 예상하고 시도조차 하지 않았다.

처음으로 코딩테스트를 하며 메모장을 꺼냈는데 막상 메모하면서 풀어보니 간단한 문제로 끝에서 초과된 만큼 빼주고 방향만 그에 맞춰서 바꿔주면 되는 문제였다.

그렇게 새 좌표의 위치를 구하고 새 좌표에서 상어의 크기를 비교하고 크기가 작으면 잡아먹는식으로 코드를 작성했으나 '틀렸습니다'

분명 모든 예제에 대해서 정답이 나왔지만 1%도 오르지 않고 가차없이 틀렸다고 나왔다.

예제 1번은 과정까지 나오니 과정까지 출력하여 디버깅을 해봤더니

문제에서 상어는 동시에 움직이고 내 코드에서 상어는 순서대로 하나씩 움직인다는 차이가 있었다.

그렇기 때문에 1번상어가 움직인 위치에 움직이지 않은 2번상어가 있으면 2번상어는 움직이지 못하고 잡아 먹히기 때문에 '틀렸습니다'가 나왔다.

이를 해결하기 위해 새로운 리스트를 만들고 상어의 새 좌표를 새로운 리스트에 할당시켜서 동시에 움직이는 것처럼 구현했더니 시간초과.....

다행히 PyPy3로 제출했더니 바로 '맞았습니다'가 나왔다.

코드가 계속 복잡해져 가니 PyPy3언어의 필요성을 느끼고 있다.

import sys
from copy import deepcopy
input = sys.stdin.readline

r,c,m = map(int, input().split())

graph = [[[0,0,0] for _ in range(c)] for _ in range(r)]
shark = []

for _ in range(m):
    x,y,v,dir,size = map(int,input().split())
    #1행 1열부터 세기 시작하므로 -1 처리
    graph[x-1][y-1] = [v,dir,size]
    #상어의 위치정보 저장
    shark.append([x-1,y-1])

#1,2,3,4로 구분되므로 0은 비우고 상,하,좌,우 순
dx = [0,-1,1,0,0]
dy = [0,0,0,1,-1]

result = 0
#각 열을 체크
for i in range(c):
    #해당 열에서 행을 추가하며 가장 가까운 상어를 잡는다.
    for j in range(r):
        if graph[j][i] != [0,0,0]:
            result += graph[j][i][2]
            shark.remove([j,i])
            graph[j][i] = [0,0,0]
            break
            
    #각 위치에 있는 상어의 이동
    new_shark = []
    new_graph = [[[0,0,0] for _ in range(c)] for _ in range(r)]
    
    while shark:
        x,y = shark.pop(0)
        v,dir,size = graph[x][y]
        graph[x][y] = [0,0,0]
        nx = x + (v*dx[dir])
        ny = y + (v*dy[dir])
        
        #상어의 새위치가 범위 내에 올 때까지
        while True:
            if nx < 0:
                nx = -nx
                #0보다 작아지면 아래쪽으로 이동
                dir = 2
            elif nx >= r:
                #좌표에서 초과한 분량만큼 r-1에서 빼주기
                #원래식 (r-1) - (nx - (r-1))을 정리한 것
                nx = ((r-1)*2) - nx
                #r보다 커지면 위쪽으로 이동
                dir = 1
            
            if ny < 0:
                ny = -ny
                #0보다 작아지면 오른쪽으로 이동
                dir = 3
            elif ny >= c:
                ny = ((c-1)*2) - ny
                #c보다 크면 왼쪽으로 이동
                dir = 4
                
            if 0 <= nx < r and 0 <= ny < c:
                break
            
        #새 좌표에있는 크기가 size보다 작다면
        #비어있으면 크기 0
        if new_graph[nx][ny][2] < size:
            #지금 상어로 갱신
            new_graph[nx][ny] = [v,dir,size]
            new_shark.append([nx,ny])
            
    shark = deepcopy(new_shark)
    graph = deepcopy(new_graph)
    
    
print(result)