백준 16236: 아기 상어 - BFS(Python/ 파이썬)

풀이

1. BFS: 현재 지점 기준으로 가장 가까운 인접한 노드들 탐색
   1.1. 최단 거리 물고기보다 현재 노드까지의 거리가 더 멀다면 탐색하지 않음
   1.2. 만약 인접 노드에 먹을 수 있는 크기 물고기 있다면 fish에 넣기
   1.3. 가까운 순, 위에 있는 순, 좌측에 있는 순으로 최단 거리 물고기 정렬
2. eat_fish: 현재 지점 기준으로 BFS 함수 실행
   2.1. 더 이상 먹을 물고기가 없다면 소요 시간 return
   2.2. 후보 물고기가 있다면 가장 가까운 물고기 먹기
   2.3.먹은 물고기 위치로 현재 위치 갱신 2부터 다시 실행

import sys
from collections import deque
input = sys.stdin.readline

dr = [-1, 0, 0, 1]
dc = [0, -1, 1, 0]

# 해당 포인트에서 가장 가까운 물고기 찾기
def bfs(r, c):
    global size

    visited = [[0] * n for _ in range(n)]
    q = deque([(r,c)])
    visited[r][c] = 1
    fish = []

    while q:
        cr, cc = q.popleft()
        # 만약 물
        if fish and fish[0][0] < visited[cr][cc]:
            continue

        for i in range(4):
            nr = cr + dr[i]
            nc = cc + dc[i]

            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                # 일단 최단 거리 방문 처리(못 감, 갈 수 있으나 못 먹음, 갈 수 있고 먹을 수 있음)
                visited[nr][nc] = visited[cr][cc] + 1
                if 0 <= arr[nr][nc] <= size[0]: # 갈 수 있음
                    q.append((nr, nc))
                    if 0 < arr[nr][nc] < size[0]: # 갈 수 있고 먹을 수 있음
                        fish.append((visited[cr][cc], nr, nc))

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


# 물고기 먹기
def eat_fish(r, c):
    global size, time

    while True:
        fish = bfs(r, c)

        if not fish:
            return time

        # 위치 갱신
        cnt, r, c = fish[0]
        time += cnt
        size[1] += 1
        # 먹은 물고기 위치 0으로
        arr[r][c] = 0

        if size[0] == size[1]:
            size[0] += 1
            size[1] = 0


n = int(input())
arr = []
size = [2, 0]
time = 0

for row in range(n):
    temp = list(map(int, input().split()))
    if 9 in temp:
        sr = row
        sc = temp.index(9)
        temp[sc] = 0

    arr.append(temp)

print(eat_fish(sr, sc))

lambda vs 그냥 sort

위 문제의 풀이 중에

sorted(fish, lambda x:(x[0],x[1],x[2]))

위와 같이 lambda를 이용하여 내부 index 순으로 요소들을 정렬하는 코드가 있다. 그러나 사실 sorted(fish)만 해도 사전순 정렬이기 때문에 결과값은 같다.

다만 내부 동작 방식은 다음과 같은 차이가 있다.

1. sorted(arr)

기본 비교 방식이므로 튜플 내부 요소를 자동으로 비교.
비교 연산만 수행되므로 추가적인 key 계산이 필요 없음.
시간 복잡도: O(n log n)

2. sorted(arr, key=lambda x: (x[0], x[1], x[2]))

key= 함수를 먼저 모든 원소에 대해 한 번씩 실행하여 key 값을 따로 저장.

그 후 key 값에 대해 정렬.

파이썬 내부 동작:
key 함수 계산 → O(n)
정렬 자체 → O(n log n) (key 값을 기준으로)

총 시간 복잡도: O(n + n log n) = O(n log n)

실제 성능

둘 다 O(n log n)이지만
1) 기본적으로 lambda는 각 비교 전에 lambda 함수 호출 오버헤드 및
새로운 튜플 생성에 따른 메모리 할당 및 복사 작업이 있으므로 sorted()가 이론상 더 빠르다.

2) 그러나 실제 백준 채점 결과는 lambda가 살짝 더 빠르게 나왔다.
워낙 사소한 차이지만 가능한 이유는 key값 캐싱을 통한 성능 개선 및 메모리 지역성 등이 있을 수 있음. 정확한 이유는 나도 모름..아는 분 알려주세요