[Baekjoon] 16236번 : 아기 상어 (Python, 구현, BFS)

[Baekjoon] 16236번 : 아기 상어 (Python, 구현, BFS)

 

목차

 

 

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

16236번: 아기 상어

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 68ms / 코드 길이 B

 

아기 상어는 자기보다 작은 크기의 물고기만 먹을 수 있다.

그러나 같은 크기의 물고기가 있는 곳을 지나갈 수 있다.

 

종료 시점 : 공간 내에 자신보다 크거나 같은 물고기만 있을 때 종료한다.

 

우선 순위 : (먹을 수 있는 모든 사이즈에 대하여) 자신보다 가까운 물고기 & 자신보다 작은 물고기 & 위쪽 물고기 우선 그 다음으로 왼쪽 물고기 우선

 

	물고기 (1순위)
물고기 (2순위)		물고기 (3순위)
	아기 상어

  

위와 같은 우선 순위를 골라내기 위해서는 매 물고기 먹방마다 먹을 수 있는 물고기들에 대한 거리를 구해야한다. 그리고 우선순위에 따라 정리된 물고기 한 마리를 먹고난 후의 반복적 조건들을 처리한 후 종료 시점까지 진행한다.

 

예제 3번을 토대로 고려해보자

 

time = 0, x = 2, y = 2, size = 2, eat(먹은 물고기 개수) = 0 (위쪽 먼저)

 

4 (Dist: ⅹ)	3 (Dist: ⅹ)	2 (Dist: 2)	1 (Dist: 3)
0 (Dist: 3)	0 (Dist: 2)	0 (Dist: 1)	0 (Dist: 2)
0 (Dist: 2)	0 (Dist: 1)	9 (아기 상어 위치)	0 (Dist: 1)
1 (Dist: 3)	2 (Dist: 2)	3 (Dist: ⅹ)	4 (Dist: ⅹ)

time = 3, x = 0, y = 3, size = 2, eat(먹은 물고기 개수) = 1

4 (Dist: ⅹ)	3 (Dist: ⅹ)	2 (Dist: 1)	9 (아기 상어 위치)
0 (Dist: 4)	0 (Dist: 3)	0 (Dist: 2)	0 (Dist: 1)
0 (Dist: 5)	0 (Dist: 4)	0 (Dist: 3)	0 (Dist: 2)
1 (Dist: 6)	2 (Dist: 5)	3 (Dist: ⅹ)	4 (Dist: ⅹ)

time = 9, x = 3, y = 0, size = 2 → 3, eat(먹은 물고기 개수) = 2 → 0

4 (Dist: ⅹ)	3 (Dist: 4)	2 (Dist: 5)	0 (Dist: 6)
0 (Dist: 2)	0 (Dist: 3)	0 (Dist: 4)	0 (Dist: 5)
0 (Dist: 1)	0 (Dist: 2)	0 (Dist: 3)	0 (Dist: 4)
9 (아기 상어 위치)	2 (Dist: 1)	3 (Dist: 2)	4 (Dist: ⅹ)

time = 10, x = 3, y = 1, size = 3, eat(먹은 물고기 개수) = 1

4 (Dist: ⅹ)	3 (Dist: 3)	2 (Dist: 4)	0 (Dist: 5)
0 (Dist: 3)	0 (Dist: 2)	0 (Dist: 3)	0 (Dist: 4)
0 (Dist: 2)	0 (Dist: 1)	0 (Dist: 2)	0 (Dist: 3)
0 (Dist: 1)	9 (아기 상어 위치)	3 (Dist: 1)	4 (Dist: ⅹ)

time = 14, x = 0, y = 2, size = 3, eat(먹은 물고기 개수) = 2

4 (Dist: ⅹ)	3 (Dist: 1)	9 (아기 상어 위치)	0 (Dist: 1)
0 (Dist: 3)	0 (Dist: 2)	0 (Dist: 1)	0 (Dist: 2)
0 (Dist: 4)	0 (Dist: 3)	0 (Dist: 2)	0 (Dist: 3)
0 (Dist: 5)	0 (Dist: 4)	3 (Dist: 3)	4 (Dist: ⅹ)

더 이상 먹을 수 있는 물고기가 없으므로 중지!

 

from collections import deque

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

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
x, y, size = 0, 0, 2

for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            x, y = i, j
            break

def bfs(x,y,size):
    distance = [[0]*n for _ in range(n)]
    visit = [[0]*n for _ in range(n)]
    small_fish = []

    q = deque()
    q.append((x,y))
    visit[x][y] = 1

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visit[nx][ny] and graph[nx][ny] <= size:
                q.append((nx,ny))
                visit[nx][ny] = 1
                distance[nx][ny] = distance[x][y] + 1
                if 0 < graph[nx][ny] < size:
                    small_fish.append((distance[nx][ny],nx,ny))

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

time, eat = 0, 0
while 1:
    smf = bfs(x,y,size)

    if len(smf) == 0:
        break

    dist, nx, ny = smf.pop(0)
    graph[x][y], graph[nx][ny] = 0, 0
    time += dist
    eat += 1

    if eat == size:
        size += 1
        eat = 0

    x, y = nx, ny
print(time)