[BFS, 구현] 백준 16236 아기 상어 python

📄 백준 16236 아기 상어 python 📄

www.acmicpc.net/problem/16236

16236번: 아기 상어

---

🤔 문제 풀이  🤔

첫번째 시도에서 정확히 구현하지 못했고 인터넷의 블로그를 참고하여 코드를 완성하였다.

 

내가 이 문제에서 놓친 포인트는

1. 처음 아기상어의  위치를 저장한 후 맵에서 아기상어 위치를 0으로 바꿔주지 않았다. (크기가 9인 상어로 인식하게 됨)
2. BFS가 사용하는 queue의 속성을 이용해 먹을 수 있는 상어를 찾은 횟수까지만 탐색을 수행하도록 한다. (count > flag: break)
3. 최소 이동횟수에서 먹을 수 있는 모든 물고기의 위치를 queue와는 다른 리스트에 저장한다.
4. 맨위 왼쪽 맨 끝에 위치한 물고기를 먼저 먹는다는 것은 (세로, 가로) 순서로 오름차순 정렬 하라는 뜻이다.

이 포인트들을 조금 더 신경쓰면 구현을 쉽게 할수 있다.

---

⌨️ 코드 ⌨️

from collections import deque

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

sx, sy = 0, 0
for i in range(n):
    for j in range(n):
        if arr[i][j] == 9:
            arr[i][j] = 0
            sx, sy = i, j
            break
size = 2
move_num = 0
eat = 0
while True:
    q = deque()
    q.append((sx, sy, 0))
    visited = [[False] * n for _ in range(n)]
    flag = 1e9
    fish = []
    while q:
        x, y, count = q.popleft()

        if count > flag:
            break
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if arr[nx][ny] > size or visited[nx][ny]:
                continue

            if arr[nx][ny] != 0 and arr[nx][ny] < size:
                fish.append((nx, ny, count + 1))
                flag = count
            visited[nx][ny] = True
            q.append((nx, ny, count + 1))

    if len(fish) > 0:
        fish.sort()
        x, y, move = fish[0][0], fish[0][1], fish[0][2]
        move_num += move
        eat += 1
        arr[x][y] = 0
        if eat == size:
            size += 1
            eat = 0
        sx, sy = x, y
    else:
        break

print(move_num)

Reference

rebas.kr/714