[python] 16236 아기상어

1. 문제 링크 및 문제

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

1-1 문제 요약

: 아기상어의 위치에서 시작하여 먹을 수 있는 최대 물고기를 구하는 문제

아기상어 초기 크기 : 2 , 위치 : 입력값중 9의 좌표
일 때 먹을 수 있는 물고기 : 1 (2는 지나갈 수만 있음)
먹을 수 있는 물고기가 여러마리 일 때 : 가장 위,가장 위도 여러마리면 가장 왼쪽 순서로 먹음

2. 해결 방법 생각해보자 ...

1. 먹을 수 있는 물고기 확인 함수 작성 , return 좌표
   1-1 return시 가장 위 가장 왼쪽 순으로 리턴
2. 물고기 위치에서 리턴받은 좌표로 이동
   2-1 이동 시 count += 거리
   2-2 이동 후 물고기 위치 해당 좌표로 변경
   2-3 먹은 물고기 == 아기상어크기 라면 아기상어크기 += 1

3. 코드

from collections import deque

N = int(input())
arr = []

# 순서대로 상어좌표, 먹은 물고기 수, 상어크기, 걸린 시간, 방향벡터
SharkX, SharkY = 0,0 
EatFishCount = 0
SharkSize = 2
count = 0
dx, dy = [-1,0,1,0],[0,1,0,-1]

for i in range(N):
    data = list(map(int, input().split()))
    arr.append(data)
    #상어 좌표
    if 9 in data:
        SharkX, SharkY = i, data.index(9)

def FindFish(x,y,size):
    visited = [[False]*N for _ in range(N)]
    distance = [[0]*N for _ in range(N)]
    location = []

    q = deque()
    q.append((x,y))
    visited[x][y] = True
    
    while q :
        x,y = q.popleft()
        for i in range(4):
            xx, yy = x + dx[i], y + dy[i]
            if xx<0 or xx>=N or yy<0 or yy>=N or visited[xx][yy]: continue
            if arr[xx][yy] > SharkSize : continue
            
            distance[xx][yy] = distance[x][y] + 1
            q.append((xx,yy))
            visited[xx][yy] = True
            if 0 < arr[xx][yy] < size :
                location.append((xx,yy,distance[xx][yy]))
    return sorted(location, key=lambda x:(-x[2],-x[0],-x[1]))


while 1 :
    # 1. 물고기 확인 함수
    result = FindFish(SharkX,SharkY, SharkSize)

    if len(result) == 0 :
        print(count)
        break

    # 2. 먹을 물고기 좌표, 거리
    x,y,dist = result.pop()

    arr[x][y], arr[SharkX][SharkY] = 0,0 
    count += dist # 2-1
    SharkX, SharkY = x,y # 2-2
    EatFishCount += 1

    if EatFishCount == SharkSize: #2-3
        EatFishCount = 0
        SharkSize += 1

! 아차차

실수

상어가 먹은 물고기 좌표, 이전 상어 위치까지 0,0 으로 만들어주는 과정을 빼먹음.

람다함수식 사용법 배웠어요

먹을 수 있는 물고기가 여러마리 일 때 , 가까우면서 가장 왼쪽 위 순으로 배열 return 방법이 이렇게 깔끔하구나 배웠다 ...

    return sorted(location, key=lambda x:(-x[2],-x[0],-x[1]))

sorted함수 , 람다함수를 활용한 정렬방법
: sorted함수의 key위치인자에 람다함수를 보내서, 함수에서 지장한 결과값에 따라서 정렬
1. sorted(location, key= ~~ )
2. key값에 람다함수를 작성해줌
lambda x:(-x[2],-x[0],-x[1])
x[2]:거리, 가까운
x[0]:x좌표, 가장 왼쪽
x[1]:y좌표, 가장 위
순으로 정렬한 결과값을 return

람다 사용하는 이유
: 코드의 간결함, 메모리의 절약

참고

https://resilient-923.tistory.com/357