[백준 17143번] 낚시왕 - Python으로 구현하기

[백준 17143번] 낚시왕 - Python으로 구현하기

 

문제 접근

• 주어진 문제대로 구현하는 구현 문제.
• 상어가 속력만큼 움직이는 것을 구현해야 하는데, 아래 규칙을 보면 반복문 횟수를 줄일 수 있다.
• [0] ~ [k] ~ [n-1] : k에 있는 상어가 n-1으로 갔다가 회전하여 0을 찍고 다시 k로 돌아오는건 (n-1-k) + (n-1) + (k) = 2*n-2이다. 따라서 상어가 움직일 수 있는 범위는 속력%(2*n-2)
• 아직 안움직인 상어를 잡어먹을 순 없으므로 새로운 2D 배열로 움직인 상어들을 저장, 비교

 

생각해볼 점

• 상어의 움직이는 처리를 좀더 깔끔하게 할 수 없을지?
• 하드 코딩으로 풀었는데, 다른 로직이 없는지 생각해보기

 

오답 분석

• 시간 초과가 많이 나는 문제로, 주어진 반복문을 최적화 할 수 있어야한다.

 

def catch_shark():
    global catch_cnt
    for row in range(R):
        if map_data[row][person]:
            catch_cnt+=map_data[row][person][2]
            map_data[row][person]=[]
            return

def shark_move():
    global map_data
    tmp_shark = [[[] for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if map_data[i][j]:
                direction = map_data[i][j][1]
                ni=i
                nj=j
                if 1<=direction<=2: # 세로방향
                    for _ in range(map_data[i][j][0]%(2*len(map_data)-2)):
                        ni=ni+di.get(direction)[0]
                        nj=nj+di.get(direction)[1]
                        if ni==-1 or ni == len(map_data):    # 끝까지 간 경우 방향전환
                            direction= 2 if direction==1 else 1
                            ni = ni + di.get(direction)[0]
                            ni = ni + di.get(direction)[0]
                            map_data[i][j][1]=direction

                elif 3<=direction<=4: # 가로방향
                    for _ in range(map_data[i][j][0]%(2*len(map_data[0])-2)):
                        ni=ni+di.get(direction)[0]
                        nj=nj+di.get(direction)[1]
                        if nj==-1 or nj == len(map_data[0]):
                            direction = 4 if direction == 3 else 3
                            nj = nj + di.get(direction)[1]
                            nj = nj + di.get(direction)[1]
                            map_data[i][j][1] = direction

                if tmp_shark[ni][nj]:   # 이미 상어가 있는 경우
                    if tmp_shark[ni][nj][2]<map_data[i][j][2]:
                        tmp_shark[ni][nj] = map_data[i][j]
                else:
                    tmp_shark[ni][nj] = map_data[i][j]
    map_data=tmp_shark


R,C,M = map(int,input().split())
map_data = [[[] for _ in range(C)] for _ in range(R)]
di = {1:[-1,0],2:[1,0],3:[0,1],4:[0,-1]}

for _ in range(M):
    r,c,s,d,z = map(int,input().split())
    map_data[r-1][c-1]=[s,d,z]

person=-1
catch_cnt=0
while person<C-1:
    person+=1   # 사람을 오른쪽 열로 이동
    catch_shark()
    shark_move()
print(catch_cnt)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!