[백준 16236번] 파이썬 - 아기 상어

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

16236번: 아기 상어

 

 

# 조건

• N x N 크기의 공간에 물고기 M마리와 아기 상어 1마리
• 한 칸에는 물고기가 최대 1마리 존재
• 아기 상어와 물고기는 모두 크기를 가지고 있고, 크기는 자연수이다.
• 최초의 아기 상어 크기 = 2, 1초에 상하좌우로 인접한 한 칸씩 이동
• 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 못 지나가고, 나머지 칸은 모두 지나간다.
• 이 때, 크기가 같은 물고기는 먹을 수 없지만, 있는 칸은 지나갈 수 있다.
• 아래의 규칙에 따라 어디로 이동할지 정한다.
  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움 요청
  • 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹고 1마리 이상이면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸까지의 개수
    • 거리가 가까운 물고기가 여러 마리면, 가장 위에 있는 물고기, 그런 물고기가 여러 마리면, 가장 왼쪽에 있는 물고기
• 이동은 1초가 걸리고 먹으면 빈 칸이 된다.
• 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가
• 공간의 상태가 주어질 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하라.
• 0 - 빈칸, 1,2,3,4,5,6 = 칸에 있는 물고기 크기, 9 - 아기 상어의 위치

 

# 접근 방법

• 현재 먹을 수 있는 물고기의 위치를 파악하여 거리를 계산 해준다.
• BFS를 통하여 이동 칸 수를 계산하고 먹는 카운트에 따라 물고기의 크기를 증가시켜 준다.
• 이 때, 크기가 아닌 거리를 통해 가까운 물고기를 먹으므로 반복문을 통해 왼쪽 위의 물고기 좌표를 구해준다.
• bfs를 이용하기 때문에 항상 최적 거리의 물고기를 만날 수 있다.
• 주의할 점
  • 상어의 위치를 찾은 후 0으로 변경 해주어야 한다.
  • 덩치가 커진 후 0으로 초기화 해주는 것도 중요

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
  
  
def bfs(shark_i, shark_j):  
    # 방문 기록  
    # 최소값을 구해줘야하므로 충분히 큰값 
    visited = [[1000000 for _ in range(N)] for _ in range(N)]  
    visited[shark_i][shark_j] = 0  
    q = deque()  
    q.append((shark_i, shark_j))  
  
    while q:  
        s_i, s_j = q.popleft()  
        # 전체 좌표까지의 거리 구해주기  
        for i in range(4):  
            ni, nj = di[i] + s_i, dj[i] + s_j  
            if 0<=ni<N and 0<=nj<N and visited[ni][nj] == 1000000:  
                # 크기가 현재 상어보다 작다면  
                if arr[ni][nj] <= shark_size:  
                    visited[ni][nj] = visited[s_i][s_j] + 1  
                    q.append((ni,nj))  
  
  
    # 먹이까지의 거리 구해주기 (거리, 좌표, 좌표)  
    # 최소거리 구해야되므로 충분히 큰 값    
    dist = [(100000, 100000, 100000)]  
  
    # 먹을 수 잇는 먹이 거리 및 좌표 달기  
    for k in range(N):  
        for l in range(N):  
            if 0 < arr[k][l] < shark_size:  
                dist.append((visited[k][l], k, l))  
      
    # 최소 거리이면서 좌표가 왼쪽 위인 먹이 위치 구해주기  
    # 반복문이 왼쪽 위부터 시작하므로 min을 사용해주면 자동으로 왼쪽 위 먹이 나온다.    
    return min(dist)  
  
  
  
N = int(input())  
arr = [[*map(int, input().split())] for _ in range(N)]  
# 상어 크기와 먹은 물고기 수, 이동 시간  
shark_size = 2  
eat_fish = 0  
move = 0  
  
# 상어위치 찾아주고 0으로 변경  
for i in range(N):  
    for j in range(N):  
        if arr[i][j] == 9:  
            shark_i, shark_j = i,j  
            arr[i][j] = 0  
            break  
    # 델타 탐색 방향  
di = [-1,0,1,0]  
dj = [0,-1,0,1]  
  
  
fish = True  
while fish:  
    # 먹이 정보 찾아주기  
    cnt, fish_i, fish_j = bfs(shark_i, shark_j)  
  
    # 먹이가 없다면 cnt는 100000 이다   
if cnt == 100000:  
        break  
  
    # 물고기 먹고 좌표로 이동  
    arr[fish_i][fish_j] = 0  
    shark_i, shark_j = fish_i, fish_j  
  
    # 걸린 시간 더해주기  
    move += cnt  
    # 먹은 카운트 체크  
    eat_fish += 1  
  
    # 덩치 커지는거 확인  
    if shark_size == eat_fish:  
        shark_size += 1  
        eat_fish = 0  
  
print(move)