백준 16236 아기상어 with Python3

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

BOJ 16236 아기상어 문제를 풀어봤습니다.

문제파악

구현문제들은 역시 문제에서 주어진 조건들을 파악해서 이해하는게 중요하다. 다행히도 문제에서 시뮬레이션 해야하는 행동에 대해서 정리해서 제시해줬고, 어떻게 구현할 지만 생각해보면 될 것 같다.

  • 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. -> ㅇㅋ
  • 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. -> 지나갈 수 있는 칸먹을 수 있는 칸을 계산할 때 유의해야겠다.
  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. -> 모든 물고기 탐색을 탐색해야하고
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. -> 밑에 규칙에서 자동으로 파생되어서 별 쓸모 없을 듯
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. -> 물고기들의 최단거리를 계속 계산해나가야할 것 같다
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. -> 최단거리를 구할 때 이 규칙이 자동으로 적용되게 만들거나, 최단거리를 구하고 나서 이 규칙을 따로 적용해야겠다

풀이

일단 현재 아기상어와 물고기의 거리를 직선계산해서 최단거리를 구하고 소요시간을 구할 수는 없습니다. “지나갈 수 있는 칸”에 대한 제약이 있기 때문이죠.

곰곰히 생각하다가 BFS로 구하면 될 것 같았습니다. BFS는 큐에 한 depth의 원소들이 뭉쳐서 있기 때문에 가까이 있는 물고기들을 찾아나가기에 적합한 알고리즘 같습니다.

맨 처음 생각했을 때는 마지막 조건을 구현할 때 “대충 순회할 때 위, 왼쪽, 오른쪽, 아래 순서로 순회하면 되지 않을까?” 라고 생각했었는데 다행히도 예제 데이터에 그러면 틀리는 반례가 있었습니다. (이게 그 섣부른 그리디 판단? 인가 싶었어요) BFS로 물고기를 찾을 때 처리를 해줬습니다.

코드

from collections import deque
from typing import Tuple

class EdibleFishDoesNotExist(Exception):
    pass

Coord = Tuple[int, int]

directions = ((-1, 0), (0, -1), (0, 1), (1, 0))

# 입력
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
shark_row, shark_col = None, None
shark_size = 2
eat_count = 0
timestamp = 0
for row in range(N):
    for col in range(N):
        if board[row][col] == 9:
            shark_row = row
            shark_col = col
            break
    if shark_row and shark_col:
        break

# 가장 가까운 먹을 수 있는(+ 문제의 우선순위 조건에 만족하는) 물고기의 칸과 그 물고기와 아기상어의 거리를 리턴합니다.
def get_nearest_edible_fish(shark_row, shark_col) -> Tuple[Coord, int]:
    """
    :return (fish_row, fish_col), distance
    """
    queue = deque()
    visited = [[False]*N for _ in range(N)]
    
    #초기화
    queue.append((shark_row, shark_col, 0))
    board[shark_row][shark_col] = 0
    visited[shark_row][shark_col] = True

    candidates = []
    candidate_distance = None

    while queue:
        row, col, distance = queue.popleft()

        if candidate_distance and distance != candidate_distance:
            return sorted(candidates)[0], candidate_distance

        if 0 < board[row][col] < shark_size:
            if not candidate_distance:
                candidate_distance = distance
            candidates.append((row, col))
        
        for direction in directions:
            new_row = row + direction[0]
            new_col = col + direction[1]
            if new_row >= N or new_col >= N or new_row < 0 or new_col < 0 : continue
            if visited[new_row][new_col]: continue
            if board[new_row][new_col] > shark_size: continue 
            visited[new_row][new_col] = True
            queue.append((new_row, new_col, distance + 1))
    
    if len(candidates) > 0:
        return sorted(candidates)[0], candidate_distance
    
    raise EdibleFishDoesNotExist

while True:
    try:
        fish_to_eat, distance = get_nearest_edible_fish(shark_row, shark_col)
        shark_row, shark_col = fish_to_eat
        board[shark_row][shark_col] = 0
        timestamp += distance
        eat_count += 1
        if eat_count == shark_size:
            eat_count = 0
            shark_size += 1
    except EdibleFishDoesNotExist:
        print(timestamp)
        break

간단하게 get_nearest_edible_fish에서 BFS 템플릿 코드를 써서 구현하고, EdibleFishDoesNotExist가 나올 때 까지 루프를 도는 코드입니다.

그리고 get_nearest_edible_fish에서 같은 거리에 있는 물고기들 중 문제의 조건을 만족하는 물고기 한마리를 구하기 위한 아이디어는 다음과 같습니다.

  • BFS를 하면 (원소가 각 물고기의 최단거리라고 합시다) (1, 1, 1, 2, 2, 2, 3, 3, 3) 이런식으로 뭉쳐서 나온다.
  • 처음 본 물고기가 1이면 1끼리 비교해서 가장 왼쪽 위에 있는 물고기를 구해야한다.
  • 그래서 “맨 처음 발견한 물고기의 거리”(candidate_distance)를 저장해놓고 일단 발견한 물고기들을 candidates에다가 저장해놓는다.
  • 물고기를 발견하다가 그 물고기의 거리와 candidate_distance가 다르면 candidate_distance인 물고기들을 모두 발견한 것이다.
  • 가장 왼쪽 위라는 조건은 tuple을 기본 순서로 정렬했을 때 첫 번째 원소라는 것과 동치이다.
  • 만약 (모두 순회했을 때 history)BFS 큐가 (1, 1, 1, 1, …) 이런식으로 구성되어있으면 candidate_distance가 달라지는 시점이 안올테니까 BFS 순회가 종료된 시점에서도 한 번 더 가장 왼쪽 위 조건을 검사해서 리턴.

Written by@cereme
프로덕트를 만들어 나가는게 너무나 즐거운 주니어 개발자

GitHubTwitter