백준 - 아기 상어(16236)

문제 링크 ▶︎ 백준 아기 상어 16236

문제 파악

1 ≤ n ≤ 20 이라는 조건 하에 시간 제한이 2초라 TLE 생각하지 않고 풀어야겠다.

먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
이라는 조건으로 시간제한을 생각하지 않고 아기 상어가 이동 할 수 있는 곳, 거리를 BFS로 다 찾고 나서 제일 가까운 거리를 기억해두고 방문하는 식으로 하면 될 것 같다.

그리고 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 이라는 조건으로 먹은 물고기의 수를 카운트하는 변수도 존재해야 할 것 같다.

또한 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 라는 조건으로 인해 상좌우하 순서로 체크해서 거리를 체크해두고 최솟값을 교체해주는 식으로 짜야할 것 같다.

접근 방법

최대한 풀어서 코드를 작성하기로 했다.
bfs를 통해서 아기상어의 사이즈와 같거나 작은 maps 를 모두 방문한다.
visit을 변경하면서 해당 좌표까지의 최소 거리를 distance에 저장해두고, 못가는 곳이면 로 초기화되어 -1있다.
다음 먹어야하는 물고기는 방문할 수 있으며, 크기는 아기상어보다 작고, 거리는 가장 가까워야하고, 상-좌에 존재해야 한다.

그러고나서 이중포문으로 maps와 visit을 탐색한다.
조건에 부합하는 곳이 나오면 바로 distance를 time에 추가하고 target좌표로 이동한다.
그 곳에서 아기상어의 위치를 변경하고 다시 반복한다.

변수 이름	변수 내용
bx, by	아기상어의 위치
shark	아기상어의 크기
eatFish	아기 상어가 먹은 물고기의 수
maps	n by n 의 공간 상태
visit	아기 상어가 해당 좌표까지 움직이는 distance 정보
target_x,y	조건에 부합해서 아기 상어가 먹어야하는 물고기 좌표
time	걸린 시간
distance	현재 아기상어가 방문할 수 있는 곳까지 거리

코드

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

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

def findDistance(maps, shark, bx, by):
    target_x, target_y = -1, -1
    distance = 400 # 넉넉한 변수 초기화값
    visit = [[-1] * n for _ in range(n)]
    q = deque()
    q.append((bx, by))
    visit[by][bx] = 0

    while q: # 방문할 수 있는 곳의 거리를 계산
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if visit[ny][nx] == -1 and shark >= maps[ny][nx]:
                    visit[ny][nx] = visit[y][x] + 1
                    q.append((nx, ny))

    for i in range(n): # 방문
        for j in range(n):
            if 0 < maps[i][j] < shark and 0 < visit[i][j] < distance:
                distance = visit[i][j]
                target_x, target_y = j, i
            else: continue
    return [target_x,target_y,distance]

    

n = int(input())  # 2 <= n <= 20
maps = []
shark = 2  # 처음 아기 상어 사이즈
time = 0  # 시간
eatFish = 0  # 먹은 물고기
bx, by = 0, 0  # 아기 상어 위치

for i in range(n):
    arr = list(map(int, input().split()))
    maps.append(arr)
    for idx, x in enumerate(arr):
        if x == 9:
            by = i
            bx = idx
            maps[by][bx] = 0

while True:
    answer = findDistance(maps, shark, bx, by)
    if answer[0] == -1 and answer[1] == -1:  # 물고기 먹을 게 없는 상황
        print(time)
        break
    else:
        bx, by = answer[0], answer[1]
        time += answer[2]
        maps[by][bx] = 0
        eatFish += 1
        if eatFish == shark:
            shark += 1
            eatFish = 0

개선 사항

문제 이해하는데 오래 걸렸다.
거리와 크기, 그리고 상좌 옵션까지 따져야 할 조건이 많아서 까다로웠다.
좀 더 깔끔하게 풀 수는 있을 것 같은데 머리가 아플 것 같다.