백준 16236 - 아기 상어

출처 : 백준, https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

 

먼저, 생각해야 할 부분

 

1. 먹을 수 있는 물고기의 위치와 거기까지의 거리를 어떻게 찾을지 생각해야한다.

2. 같은 거리의 물고기 중 위 왼쪽에 위치한 물고기를 찾아야한다.

 

---

 

풀이

import sys
from collections import deque

KEY_SIZE = 'size'
KEY_EAT_FISH = 'eatFish'
KEY_POINT = 'point'

def input():
    return sys.stdin.readline().strip()

# BFS에서 같은 거리를 전부 뽑는다.
# 가장 가까운 거리에 있는 먹을 수 있는 것을 뽑는다. 같은 거리 내에서 상단 같다면 왼쪽에 있는 애를 뽑는다.
def BFS(seaMap, babyShark, visitedMap):
    global KEY_SIZE
    global KEY_POINT
    global KEY_EAT_FISH

    VISITED = 1
    BLANK = 0

    ROW_LENGTH = len(seaMap)
    COL_LENGTH = len(seaMap[0])

    currentPoint = babyShark[KEY_POINT]
    sharkSize = babyShark[KEY_SIZE]

    queue = deque([currentPoint])
    i, j = currentPoint
    visitedMap[i][j] = VISITED

    levelCount = 1
    distance = 0

    minNode = (999, 999)

    # queue를 돌면서 가장 가까운 먹을 수 있는 물고기를 찾는다.
    while len(queue) > 0:
        i, j = queue.popleft()
        levelCount -= 1

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

        for idx in range(4):
            ni, nj = i + dx[idx], j + dy[idx]
            
            # 주위 상하좌우 칸 중에서 방문하지 않은 올바른 칸 중 상어가 지나갈 수 있는 칸을 queue에 넣음
            if 0 <= ni < ROW_LENGTH and 0 <= nj < COL_LENGTH and visitedMap[ni][nj] != VISITED:
                if seaMap[ni][nj] <= sharkSize:
                    visitedMap[ni][nj] = VISITED
                    queue.append((ni, nj))

        if seaMap[i][j] != BLANK and seaMap[i][j] < sharkSize:
            # 먹을 수 있는 물고기가 나오면, minNode를 업데이트한다.
            # 기본적으로 튜플은 i, j순으로 비교되므로, 가장 위, 왼쪽이 더 작다.
            if (i, j) < minNode:
                minNode = (i, j)

        if levelCount == 0:
            # 같은 거리에 있는 칸을 전부 둘러봤다면, 그 다음 거리 개수 업데이트
            levelCount = len(queue)

            if minNode != (999, 999): # 만약 먹을 수 있는 고기가 있다면 return
                return (minNode, distance)
            
            # 거리 + 1
            distance += 1

    return (False, 0)

def solution(n, seaMap):
    global KEY_SIZE
    global KEY_POINT
    global KEY_EAT_FISH

    SHARK = 9

    answer = 0

    # 상어 정의
    babyShark = dict()
    babyShark[KEY_SIZE] = 2
    babyShark[KEY_EAT_FISH] = 0
    babyShark[KEY_POINT] = None

    for i in range(n):
        for j in range(n):
            if seaMap[i][j] == SHARK:
                babyShark[KEY_POINT] = (i, j)
                seaMap[i][j] = 0
                break

        # 상어 위치 찾으면 break
        if babyShark[KEY_POINT] != None:
            break

    visitedMap = [[0 for _ in range(n)] for _ in range(n)]

    while True:
        # 먹을 수 있는 위치와 거기까지 이동 거리
        result, distance = BFS(seaMap, babyShark, visitedMap)

        # 먹을 수 있는 위치가 없다면, break
        if result == False:
            break
        else:
            # 거리 누적
            answer += distance
            # 상어 이동
            babyShark[KEY_POINT] = result
            # 상어 물고기 잡아먹음
            babyShark[KEY_EAT_FISH] += 1

            fi, fj = result
            # 물고기 주금
            seaMap[fi][fj] = 0

            # 상어가 크기만큼의 물고기 개수를 먹었다면, 상어 성장
            if babyShark[KEY_EAT_FISH] == babyShark[KEY_SIZE]:
                babyShark[KEY_SIZE] += 1
                babyShark[KEY_EAT_FISH] = 0

            visitedMap = [[0 for _ in range(n)] for _ in range(n)]

    return answer

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

print(solution(n, seaMap))

---

 

고찰

 

BFS 처리할 때 동일한 거리를 전부 보고 결정을 내려야할 때는 queue의 길이를 업데이트하는 방법도 나쁘지 않다.

 

Github

아기 상어