[백준 17143번] 낚시왕(파이썬)

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

17143번: 낚시왕

 

이 문제는 이름 그대로

사람을 낚는 문제.

정답률이 25%이하인 문제치고

문제에서 요구하는 것이

어렵지 않아 보였습니다.

저도 요구하는 걸 다 나열해보고

'별거 아니네'

하고 넘어갔다가

시간초과가 떠서 참 애를 먹었습니다.

풀다보니깐

최적화라는 관점에서

문제를 공부하게 되었습니다.

 

구현할 건 크게 3가지

 

1. 낚시왕이 이동

 

2. 현재 위치한 열에서

가장 땅에 가까운 상어를 포획

 

3. 상어들끼리 이동

(상어가 서로 겹치면

가장 큰 상어만 살아남음)

 

graph에 각각의 상어의 위치에

크기 속도 방향을 넣어주면 됩니다.

 

R,C,M=map(int,input().split())
shark=[]
graph=[[[] for _ in range(C)] for _ in range(R)]
for i in range(M):
  r,c,s,d,z=map(int,input().split())
  graph[r-1][c-1].append([z,d,s])
  shark.append([r-1,c-1,z])

 

이렇게 graph를 선언해주면 완성.

 

상어 이동시켜줄 때,temp를 써서 이동시켜줍니다.

https://door-of-tabris.tistory.com/entry/%EB%B0%B1%EC%A4%80-19237%EB%B2%88-%EC%96%B4%EB%A5%B8%EC%83%81%EC%96%B4%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준 19237번] 어른상어(파이썬)

이 문제에서와 비슷한 경우인데

바로 graph로 옮겨주면

한번 옮긴 상어를

또 옮겨주는 실수를 범하게 됩니다.

그래서 graph와 같은 크기의

temp를 선언해주고

temp에다가 이동을 시킨 걸 넣어줍니다.

그리고 넣다가

길이가 2개가 되면

sort()를 시킨 후

맨 앞(index 0)을 제거하면 됩니다.

sort로 정렬하면

작은 순서대로 정렬이 되기 때문.

 

이렇게 하다가....

시간초과가 떠서

진짜 별 똥꼬쇼를 다했습니다.

 

최적화를 하기 위해

for문을 최소화하자.

 

처음에 그래프를 다 돌면서

상어가 있는 위치를 찾았다면,

이제는 미리 상어의 위치를 받은 후에

각각에 맞춰서 상어를 꺼냈습니다.

원래는 R*C만큼 돌린 걸

현재 상어의 갯수만큼 돌려주니

시간절약 달성!

인데...여전히 시간초과로 막혔습니다.

 

이유는 바로 상어의 이동 때문이었습니다.

 

3X4격자에 

속력을 100000까지 높여보겠습니다.

그럼 상어가 계속 왔다갔다를 반복합니다.

저의 경우, 100000까지 상어가 계속 이동하는 걸로

우직하게 풀이를 하다보니

반복문이 100000번을 돌아서

시간초과가 발생하게 되었습니다.

그럼 이걸 최적화 시켜야 겠죠?

이런 논리로

중복이 되는 경우를 최소화시킨다면

시간초과가 극복이 됩니다.

 

# 17143번 낚시왕
from copy import deepcopy

R, C, M = map(int, input().split())
shark = []
graph = [[[] for _ in range(C)] for _ in range(R)]
for i in range(M):
    r, c, s, d, z = map(int, input().split())
    graph[r - 1][c - 1].append([z, d, s])
    shark.append([r - 1, c - 1, z])

shark_check = [True] * M

dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]

king_x = 0
king_y = -1

catch = 0

# print(shark)
# print(graph)
while True:
    # 1 낚시왕이 한 칸 이동
    king_y += 1
    if king_y >= C:
        break
    if not shark:
        break
    # print(king_y+1)
    # 2.현재열에서  가장 작은 행에 있는 상어제거
    for x in range(R):
        if graph[x][king_y]:
            catch += graph[x][king_y][0][0]
            size = graph[x][king_y][0][0]
            for i in range(len(shark)):
                if shark[i][2] == size:
                    shark.pop(i)
                    break
            graph[x][king_y].clear()

            break
    temp = [[[] for _ in range(C)] for _ in range(R)]
    # 3. 상어이동
    d_shark = []
    for sh in range(len(shark)):

        # print(graph)
        s_x, s_y = shark[sh][0], shark[sh][1]
        # print(s_x,s_y)
        z, d, s = graph[s_x][s_y].pop()
        moving = 0
        nx = s_x
        ny = s_y

        # 왕복하는 것 최적화시켜준다
        # 이거 해결하니 시간초과가 풀리네...ㅎㄷㄷ
        # 위아래로 움직이는 경우
        if d <= 2:
            s %= (R - 1) * 2

        # 좌우로 움직이는 경우
        else:
            s %= (C - 1) * 2

        while moving < s:
            nx += dx[d]
            ny += dy[d]
            # 경계를 벗어나는 케이스
            if nx < 0 or nx >= R or ny < 0 or ny >= C:
                nx -= dx[d]
                ny -= dy[d]
                if d == 1:
                    d = 2
                elif d == 2:
                    d = 1
                elif d == 3:
                    d = 4
                elif d == 4:
                    d = 3
                nx += dx[d]
                ny += dy[d]
            moving += 1

        temp[nx][ny].append([z, d, s])
        shark[sh][0] = nx
        shark[sh][1] = ny
        # 이동중, 만약에 격자에 2마리가 모일 경우
        if len(temp[nx][ny]) == 2:
            temp[nx][ny].sort()
            dele = temp[nx][ny][0][0]
            d_shark.append(dele)
            temp[nx][ny].pop(0)

    while d_shark:
        eat = d_shark.pop()
        for i in range(len(shark)):
            if shark[i][2] == eat:
                shark.pop(i)
                break

    graph = deepcopy(temp)
    # print(graph)
    # print(shark)
    # print()

print(catch)

물론, 이 코드도

완전히 최적화에 성공한 케이스는 아닙니다.

왜냐하면 pypy3로만 통과가 되기 때문이죠.

 

https://hoyeonkim795.github.io/posts/17143/

[백준] #17143 낚시왕 python (파이썬)

https://juhi.tistory.com/47

[Python] 백준 17143 : 낚시왕

여기보시면

최적화에 더 진심인 코드가 있습니다.

이걸 보시면서

공부를 더 하셔도 됩니다.

 

반복문이 많아지면

최적화가 깨질 수 있다.

그 반복문을 어떻게 줄일 것인가에 대한

공부를 할 수 있었습니다.

 

+++

#백준 17143 낚시왕
from copy import deepcopy
R,C,M=map(int,input().split())

graph=[[[]for _ in range(C)] for _ in range(R)]

dx=[-1,1,0,0]
dy=[0,0,1,-1]

for _ in range(M):
    x,y,s,d,z=map(int,input().split())
    x-=1
    y-=1
    d-=1
    graph[x][y]=[s,d,z]

answer=0
for king in range(C):
    #왕이 물고기를 먹어줌
    now=0
    while now<R:
        if graph[now][king]:
            answer+=graph[now][king][2]
            graph[now][king]=[]
            break
        now+=1
    temp=[[[]for _ in range(C)] for _ in range(R)]
    for x in range(R):
        for y in range(C):
            if graph[x][y]:
                s,d,z=graph[x][y]
                #위 아래로 움직이는 경우
                if d==0 or d==1:
                    s=s%(2*(R-1))
                #좌우로 움직이는 경우
                elif d==2 or d==3:
                    s=s%(2*(C-1))
                nx=x
                ny=y
                move=0
                while move<s:
                    nx+=dx[d]
                    ny+=dy[d]
                    if nx<0 or nx>=R or ny<0 or ny>=C:
                        nx-=dx[d]
                        ny-=dy[d]
                        if d==0: d=1
                        elif d==1 :d=0
                        elif d==2 :d=3
                        elif d==3:d=2

                    else:
                        move+=1
                #이동한 곳에 상어가 있을 경우
                if temp[nx][ny]:
                    n_size=z
                    go_size=temp[nx][ny][2]
                    #지금 움직이는 상어가 더 크다면, 지금 상어로 최신화(큰 걸로 먹는다는 개념)
                    if n_size>go_size:
                        temp[nx][ny]=[s,d,z]

                else:
                    temp[nx][ny]=[s,d,z]

    graph=deepcopy(temp)

print(answer)

새로 다시 푼 버전.

좀 더 가독성있게 코드를 재구성했습니다.