16236 - 아기 상어

 

---

 

문제

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

16236번: 아기 상어

 

풀이

bfs 기반 빡(?)구현 문제이다.

 

bfs로 계속 탐색을 하면서 현재 물고기 크기에서 먹을 수 있는 물고기를 모두 찾아본다.

단 탐색시에 자신보다 큰 물고기를 지나갈 수 없고, 같은 크기의 물고기는 지나는 가되 먹을 물고기에 추가하지는 않는다.

 

그렇게 현 상황에서 먹을 수 있는 모든 물고기를 저장해둔 배열을 다중 조건으로 정렬해줘야한다.

1. 크기

2. 크기가 같다면 열 오름차순 (가장 위에 있는 물고기)

3. 행도 같다면 행 오름차순 (가장 왼쪽에 있는 물고기)

 

위 세 조건을 걸고 정렬 후 리스트 첫번째 물고기를 먹어주면 된다.

거리 저장해주고, 물고기 크기를 키울지도 판단해준다.

먹은 후에는 기존 물고기 위치를 빈칸으로 변경하고, 먹은 물고기 위치로 옮겨준다.

 

이 과정을 계속 반복하고, 더이상 먹을 물고기가 없다면 저장해둔 거리를 출력해주면 답이다.

 

 

코드

from collections import deque

def getfishes(x, y):

    global space, scale, answer, n, count
    ox, oy = x, y
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    visited = [[False] * n for _ in range(n)]

    # 큐에 상어 위치 넣어준다.
    q = deque()
    q.append((x,y,0))
    visited[x][y] = True
    fishes = []
    while q:
        x, y, cost = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                # 잡아먹을 수 있다면
                if space[nx][ny] <= scale and not visited[nx][ny]:
                    # 빈칸이 아니거나, 작다면 먹는 목록에 더해준다.
                    if space[nx][ny] != 0 and space[nx][ny] < scale:
                        fishes.append((cost+1,nx, ny))
                    visited[nx][ny] = True
                    q.append((nx, ny, cost+1))

    if not fishes:
        return -1, -1

    # fishes[i] = [거리, x좌표, y좌표]
    # 가장 가까운 순, 가장 높은 순, 가장 왼쪽 순으로 다중 정렬한다.
    fishes = sorted(fishes, key = lambda l : (l[0], l[1], l[2]))

    # 먹을 친구 정한다.
    target = fishes[0]

    # 거리를 더해준다.
    answer += target[0]

    # 물고기 수 더해주고, scale 을 키울지 여부 체크한다.
    count += 1
    if count == scale:
        scale +=1
        count = 0

    x, y = target[1], target[2]

    # 물고기를 옮겨준다.
    space[ox][oy] = 0
    space[x][y] = 9

    return x, y

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

scale = 2
answer = 0
x = y = 0
count = 0
for i in range(n):
    for j in range(n):
        if space[i][j] == 9:
            x, y = i, j

while True:
    x, y = getfishes(x, y)
    if x == -1 and y == -1:
        break

print(answer)

 

후기

 

다중정렬이 귀찮은 요소로 작용할수도 있는데, 파이썬의 다중정렬은 정말 편하다!