[백준/Python] 아기 상어

 

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

 

---

도움

https://velog.io/@waoderboy/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-16236-%EC%95%84%EA%B8%B0%EC%83%81%EC%96%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC

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

 

BFS를 사용한다

 

bfs를 이용하여 먹이를 먹으러 갈 수 있는 곳 중 최단 거리 확인

 

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다 

-> sh_shape(자신의 크기), eat(물고기 몇 개 먹었는지) 변수 사용

아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지

-> cnt 변수 사용

현재 상어의 x,y 위치

-> babyx, babyy 변수 사용

 

라이브러리

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

 

bfs 함수

def bfs(startx, starty):
    visited = [[0]*n for _ in range(n)]
    q = deque([(startx, starty)])
    visited[startx][starty] = 1
    # 아기상어가 먹을 수 있는 물고기의 거리와 좌표를 저장할 리스트
    cand = []
    
    while q:
        nowx, nowy = q.popleft()

        for dx, dy in [(-1,0), (0,-1), (1,0), (0,1)]:
            x = nowx + dx
            y = nowy + dy

            if 0<=x<n and 0<=y<n and visited[x][y] == 0:
                g = graph[x][y]
                if g == 0: # 빈 칸이면
                    visited[x][y] = visited[nowx][nowy]+1
                    q.append((x,y))
                elif g < sh_shape: # 물고기를 먹을 수 있음
                    visited[x][y] = visited[nowx][nowy]+1
                    cand.append((visited[x][y]-1, x, y)) # 거리, 행, 열
                elif g == sh_shape: # 물고기를 먹을 수는 없고 이동은 가능
                    visited[x][y] = visited[nowx][nowy]+1
                    q.append((x,y))
    # 거리, 거리가 같다면 더 위에 있는 행, 거리와 행이 같다면 더 왼쪽에 있는 열
    return sorted(cand, key = lambda x: (x[0], x[1], x[2]))

 

입력 받기

n = int(input())
graph = []
for i in range(n):
    l = list(map(int, input().split()))
    graph.append(l)
    
    for j in range(n):
        if l[j] == 9:
            babyx, babyy = i,j

 

len(v)가 0일 때 -> 먹을 수 있는 물고기가 없을 때

sh_shape = 2
cnt = 0
eat = 0
while True:
    v = bfs(babyx, babyy)
    if len(v) == 0:
        print(cnt)
        break
    else:
        # print(v)
        cnt += v[0][0]
        eat += 1
        graph[babyx][babyy] = 0
        babyx, babyy = v[0][1], v[0][2]
        
        if eat == sh_shape:
            sh_shape += 1
            eat = 0