백준 17143번 낚시왕 삼성 SW역량테스트 (Python, 구현)

백준 17143번 낚시왕 문제 바로가기

문제 이해

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

낚시왕이 오른쪽으로 한 칸 이동한다.
낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
상어가 이동한다.
상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

문제 접근

문제를 보고 3가지로 나누어 생각했다.

• 낚시왕 한칸 이동
• 땅과 가장 가까운 상어 잡기
• 상어 이동 -> 같은 칸 상어 잡아먹기

구현만 하기는 쉬운 문제이다.
하지만 최적화하기 조금 복잡한것같다.
내가 푼 방법은 pypy3에서만 동작하기 때문에 좋은 코드는 아니다.
내 코드에서 최적화해야할 부분들을 표시해두겠다.
아직 많이 부족하다는 것을 느꼈고, 같은 정답도 메모리, 수행시간면에서 큰 차이가 있을 수 있다는 것을 알 수 있었다.

문제 풀이

낚시왕 한칸 이동

낚시왕이 한칸 이동하는것을 반복문을 사용하여 구현했다.
따라서 땅과 가장 가까운 상어잡기와 상어 이동은 이 반복문 내에서 동작해야 할 것이다.

for i in range(C):

땅과 가장 가까운 상어 잡기

나는 pan이라는 지도에 각각의 칸에 리스트를 넣었다. 따라서 pan은 3차원 리스트이다.
pan의 각각의 칸에는 상어의 리스트들이 들어가있다.
상어의 리스트를 발견하면 상어 한마리를 잡음을 표현하기 위해 pop하고 result에 그 상어의 크기를 더하고 반복문을 탈출한다. (땅에서 더 멀리있는 상어를 또 잡지 않기 위해)

 for j in range(R):
        if pan[j][i]:
            s,d,z = pan[j][i].pop()
            result += z
            break

상어 이동 (최적화해야 할 부분)

상어의 리스트를 전부 뽑아낸 후에
상어를 이동시킨다.
for문을 사용해서 s만큼 반복한다. dx와 dy를 사용해서 1씩 증감하기 때문에 많은 시간을 이 부분에서 잡아먹는다.
벽에 닿았을 때 방향을 전환해준다. 모든 s를 이동했다면 새로운 위치 j,k에 다시 s,d,z를 추가해준다.

 # 상어 이동
    for j in range(R):
        for k in range(C):
            if pan[j][k]:
                s,d,z=pan[j][k].pop()
                shark.append([j,k,s,d,z])
    while shark: # 최적화 해야할 부분
        j,k,s,d,z = shark.pop()
        for _ in range(s):
            j = j+dx[d-1]
            k = k+dy[d-1]
            if k<0 or j<0 or j>R-1 or k>C-1:
                if d==1:
                    d=2
                elif d==2:
                    d=1
                elif d==3:
                    d=4
                elif d==4:
                    d=3
                j = j+2*dx[d-1]
                k = k+2*dy[d-1]
        pan[j][k].append([s,d,z])

같은 칸 상어 잡아먹기

상어의 리스트의 크기가 2 이상인 위치에서 while문을 통해 1마리만 남기고 모두 pop한다.

 # 같은 자리에 있는 상어 잡아먹기
    for j in range(R):
        for k in range(C):
            if len(pan[j][k])>=2:
                pan[j][k].sort(key=lambda x:-x[2])
                while len(pan[j][k])>1:
                    pan[j][k].pop()

제출 코드

import sys
R,C,M = map(int, sys.stdin.readline().split())
shark_input = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
pan = [[[] for i in range(C)] for _ in range(R)]
# 낚시왕 한칸 이동
# 땅과 가장 가까운 상어 잡기, 사라짐
# 상어 이동
shark = []
#  (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
while shark_input:
    r,c,s,d,z = shark_input.pop()
    pan[r-1][c-1].append([s,d,z])
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
# 낚시왕 이동
for i in range(C):
    # 땅과 가장 가까운 상어 잡기
    for j in range(R):
        if pan[j][i]:
            s,d,z = pan[j][i].pop()
            result += z
            break
    # 상어 이동
    for j in range(R):
        for k in range(C):
            if pan[j][k]:
                s,d,z=pan[j][k].pop()
                shark.append([j,k,s,d,z])
    while shark:
        j,k,s,d,z = shark.pop()
        for _ in range(s):
            j = j+dx[d-1]
            k = k+dy[d-1]
            if k<0 or j<0 or j>R-1 or k>C-1:
                if d==1:
                    d=2
                elif d==2:
                    d=1
                elif d==3:
                    d=4
                elif d==4:
                    d=3
                j = j+dx[d-1]
                k = k+dy[d-1] 
                j = j+dx[d-1]
                k = k+dy[d-1] 
        pan[j][k].append([s,d,z])
    # 같은 자리에 있는 상어 잡아먹기
    for j in range(R):
        for k in range(C):
            if len(pan[j][k])>=2:
                pan[j][k].sort(key=lambda x:-x[2])
                while len(pan[j][k])>1:
                    pan[j][k].pop()
print(result)