[BOJ 16236][백준 16236번] 아기상어 (파이썬 풀이)

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

 

🤔 문제 설명 및 입출력

---

 

 

✍ 접근 방법

---

문제의 핵심은 "상어가 먹을 수 있는 물고기 중 가장 가까운 물고기를 찾아라" 이다.

 

"가장 가까운 대상 찾기 + 입력이 행렬 꼴 " 이면 대부분의 문제는 BFS를 활용하여 풀이한다. 얼핏 보면 문제에 조건이 엄청 바리바리 달려있어서 복잡해보이지만, 상어의 크기가 커지는건 크게 어려운 부분이 아니라, 주어진 입력에 대해 다음 시퀀스를 반복하면 된다.

 

1. 잡아먹을 수 있는 물고기를 찾는다
2. 찾은 물고기들 중 가장 가까운 놈들 잡아먹는다
3. 행렬을 갱신한다. ( 잡아 먹은놈 행렬에서 삭제)
4. 크기를 키울 수 있으면 키운다
5. 더 이상 잡아 먹을 수 없을 때까지 반복한다.

여기서 포인트는 잡아먹을 수 있는 "물고기 중 가장 가까운 놈을 어떻게 판별 하느냐?" 인데, 한바탕 탐색이 끝나고 먹을 수 있는 물고기들을 모종의 방법으로 sort 해도 되지만, 우리에겐 잘 만들어진 바퀴인 heapq 모듈이 있다. heapq는 최소힙을 구현한 모듈로, 밀어넣은 순서에 상관없이 가장 작은 값이 제일 앞에 나오는 구조를 가지고 있다. 그럼 우리는 물고기의 거리 정보를 기준으로 heapq를 만들면, 복잡한 계산 필요없이 가장 가까운 물고기를 찾을 수 있지 않을까???

 

 

이 아이디어를 머리 속에 간직한채로, 알고리즘을 구현해보자.

 

 

 

 

⬇ heapq 공식문서

---

https://docs.python.org/ko/3/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.9.5 문서

 

👨‍💻 소스 코드

---

• 파이썬

from collections import deque
import heapq

# 기본 아이디어 : 일단 보이는 물고기 다 먹는다. -> 먹은 물고기 위치, 먹기까지 걸린 시간 모두 저장 -> 먹기까지 가장 적게 걸린 시간 반환 -> 그러기 위해 최소힙으로 저장

def BFS(lst:list):
    pray = []
    visited = [[False] * N for _ in range(N)]
    queue = deque([lst])

    # 델타 무브 상하좌우
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    while queue:
        x,y,level = queue.popleft()
        for i in range(4):
            new_x = x + dx[i]
            new_y = y + dy[i]
            if 0<=new_x<N and 0<=new_y<N and not visited[new_x][new_y]:
                visited[new_x][new_y] = True
                # sea[new_x][new_y] <= shark_size로 퉁치면 안되는 이유 :
                # shark_size보다 작은 물고기들은 먹어야 ( 힙에 넣어야 ) 하기 때문이다.
                if sea[new_x][new_y] == shark_size or sea[new_x][new_y] == 0:
                    queue.append([new_x,new_y,level+1])
                elif sea[new_x][new_y] < shark_size:
                    heapq.heappush(pray,[level+1,new_x,new_y])
    if pray:
        return pray[0]
    else:
        return None


N = int(input())
# 일단 상어 위치 찾아야지


fish = []
sea = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if sea[i][j] == 9:
            shark = [i,j]
            x,y = i,j
        elif 1<= sea[i][j]<=6:
            fish.append([i,j])

level = 0
count = 0
ate = 0
shark_size = 2
while fish:
    # 다른 미로문제와는 다르게, 큐가 다 떨어졌어도, 조건에 따라 왔던곳도 다시 이동할 수 있다.
    # 그러니까 다시 방문행렬을 새로 만드는 것
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True
    result = BFS([x,y,level])
    # result가 있다 --> 뭐라도 잡아왔다
    # result[0] : 물고기 잡은 시간
    # result[1] : 물고기 x 좌표
    # result[2] : 물고기 y 좌표
    if result:
        count += result[0]
        x,y = result[1],result[2]
        fish.remove([result[1],result[2]])
        sea[result[1]][result[2]] = 0
        ate += 1
    else:
        break

    if ate >= shark_size:
        shark_size += 1
        ate = 0

print(count)

 

• queue는 list를 가져다 써도 되지만, 제 구현에서는 list를 쓰면 시간초과가 나서 deque를 가져다 썼습니다.
• result는 잡아온 물고기의 정보를 담는 변수이며, 먹을 수 있는 물고기가 있는 한 무조건 어떤 결과값을 반환합니다.근데 이게 비어있다? 그럼 더 이상 먹을 수 있는 물고기가 없다는 뜻이므로 break 해줘서 물고기가 남아있더라도 빠져나가게 합니다.
• 주석에도 적혀있지만, 이 문제는 BFS 표준문제인 미로문제와 다르게, 한번 왔던 길을 다시 이동할 수 있습니다. ( ex.물고기 잡아먹고 몸집이 커졌는데, 커지고 보니까 먹을 놈이 또 있는 경우 ⬅ 왔던 길 상관없이 다시 먹으러 가야함)

 

🔥 강평

---

처음 이 문제를 봤을때는 굉장히 당황스러웠습니다. 분명 BFS로 푸는 건 맞는데....뭐 이렇게 복잡하지??? 라는 생각이 들었지만, 다른 분들 힌트를 참고해서 풀어보니...... 여전히 어려웠습니다.🤣🤣🤣🤣

 

하지만 수적천석이라고, 시간 날때마다 코드를 다시 읽어보니까, 풀이의 흐름이 명확하게 보이기 시작했습니다. 이해가 안되었던 이유는 아마 heapq 모듈이 생소했기 때문이라는 생각이 드는데, 그것만 익숙해지니 정말 별거 없다..라는 생각이 들었습니다.

 

heapq를 이용해 매 탐색마다 가장 가까이에 있는 먹을 수 있는 물고기를 찾는다.

 

 

이 아이디어만 잘 가지고 계신다면 분명 쉽게 해결 하실 수 있을 것입니다.