아기 상어(백준 16236, python)

문제 설명

구현 문제가 그렇듯이 문제를 잘 이해해야 한다. 구현 자체는 어렵지 않아도 조건을 제대로 보지 않으면 나처럼 시간을 잡아 먹을 수 있다.

 

1. NxN 크기의 공간에 물고기가 M 마리가 있고 아기 상어가 1마리 있다.

2. 물고기가 있는 칸에는 물고기의 크기에 상관 없이 물고기가 한 마리만 있다. 나는 이 부분에서 물고기 크기 대로 물고기가 있는 줄 알고 구현했다가 한 30분인가 헤맸다. 하...

3. 아기 상어는 상하좌우로 한 칸씩만 이동한다. 이때 이동할 때마다 1초만큼 시간이 걸린다.

4. 아기 상어는 자기보다 작거나 같은 크기의 물고기는 지나갈 수 있지만, 자기보다 작은 물고기만 먹을 수 있다. 즉, 자기와 크기가 같은 물고기는 지나갈 수만 있고 먹을 수는 없다.

5. 먹을 수 있는 물고기가 1마리라면 해당 물고기를 먹는다.

6. 먹을 수 있는 물고기가 1마리보다 많으면 거리가 짧은 물고기를 먹는다. 거리가 짧은 물고기가 여러 마리면 가장 위에 있는 물고기를 먹는다. 거리가 짧고 가장 위에 있는 물고기가 여러 마리면 가장 왼쪽에 있는 물고기를 먹는다.

7. 아기 상어가 물고기를 먹을 때는 시간이 걸리지 않는다. 그렇기에 먹을 수 있는 칸으로 옮겼으면 시간은 1초만 걸린다.

8. 만일 더이상 먹을 수 있는 물고기가 없으면 엄마에게 도움을 요청한다.

9. 아기 상어가 자신의 크기만큼 물고기를 먹으면 아기 상어의 크기가 하나 커진다.

 

햐... 조건 많다.

골드 3 구현이라서 그런지 침착하게 구현을 해주지 않으면 문제 풀기가 곤란 할 수 있다.

 

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

16236번: 아기 상어

문제 풀이

첫 번째 접근

도대체 어떻게 풀어야 할까?

일단 이런 문제를 접했을 때는 한 번에 해결하기 보다 모든 경우를 돌아보는 걸 생각해야 한다.

 

첫 번째 해야 할 것.

아기 상어의 위치를 찾은 후, 해당 위치에서부터 먹을 수 있는 물고기가 있는 모든 위치를 찾아서 반환한다. 이때 모든 칸을 돌면서 넓이 우선 탐색을 시행한다.

일단 아기 상어의 크기보다 작거나 같은 숫자는 모두 방문해준다. 이때 해당 위치까지 얼마나 시간이 걸렸는지를 좌표와 함께 저장해줘야 한다. 그리고 아기 상어가 먹을 수 있는 물고기가 있는 칸. 즉, 0이 아니면서 아기 상어의 크기보다 작은 칸은 따로 리스트에 넣어야 한다.

 

그리고 넣어준 리스트가 0이 아닌지 확인한다. 0이 아니면 상어가 먹을 수 있는 물고기가 존재한다는 의미이므로 거리, 열좌표, 행좌표 순으로 오름차순 정렬한다. 그리고 이렇게 정렬한 배열을 반환한다. 만일 크기가 0이라 상어가 먹을 수 있는 물고기가 없으면 그냥 빈 배열을 반환한다.

 

두 번째 해야 할 것.

반환 받은 배열에 값이 없으면 전체 반복문을 탈출한다. 만일 배열에 값이 하나 이상 있어 먹을 수 있는 물고기가 있으면 제일 앞에 있는 것(위의 BFS에서 미리 정렬해줬음)을 하나 뺀다.

정답에 제일 앞에 있는 값의 거리를 더해준다. 그리고 물고기를 하나 먹었다는 표시로 먹은 물고기를 하나 더해준다. 후에 만일 지금껏 먹은 물고기가 아기 상어의 크기와 같다면 상어를 하나 더해주고 먹은 물고기를 0으로 표시해준다. 그리고 해당 좌표를 먹었다는 표시로 0을 초기화 한 후, 상어의 위치를 해당 좌표로 바꿔주면 된다.

 

다시 한 번 말하지만, 물고기는 크기와 상관 없이 한 칸에 한 마리 들어 있다. 물고기 크기 만큼 먹은 물고기를 올려서 시간을 잡아먹는 실수를 하지 말길 바란다...

 

코드

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
graph = []

dY = [-1, 0, 1, 0]
dX = [0, 1, 0, -1]

# 초기 그래프 입력
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split(" "))))


# 현재 상어의 크기로 먹을 수 있는 물고기까지 가는 모든 거리를 구하는 함수
def findFishes(shark, sharkY, sharkX):
    q = deque()
    q.append((0, sharkY, sharkX))
    visit = [[False for _ in range(n)] for _ in range(n)]
    visit[sharkY][sharkX] = True
    count = []

    while q:
        cL ,cY, cX = q.popleft()

        for k in range(4):
            nY = cY + dY[k]
            nX = cX + dX[k]

            if 0 <= nY < n and 0 <= nX < n:
                if graph[nY][nX] <= shark: # 지나갈 수 있는 위치
                    if visit[nY][nX] == False:
                        visit[nY][nX] = True
                        q.append((cL+1, nY, nX)) # 지나갔다는 표시로 큐에 넣어준다.
                        if graph[nY][nX] != 0 and graph[nY][nX] < shark: # 만일 칸에 물고기가 있는데 아기 상어의 크기보다 작아서 먹을 수 있으면 리스트에 넣는다.
                            count.append((cL+1, nY, nX))

    # 먹을 수 있는 물고기가 존재
    if len(count) != 0:
        # 거리가 제일 짧은 것 -> 제일 위에 있는 것 -> 제일 왼쪽에 있는 것
        newCount = sorted(count, key=lambda x: (x[0], x[1], x[2]))

        # print(newCount)
        return newCount

    return count


shark = 2
answer = 0
startY = 0
startX = 0
saveFish = 0

for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            startY = i
            startX = j
            graph[i][j] = 0
            break

while True:
    fishDist = []
    fishDist = findFishes(shark, startY, startX)

    # 더이상 먹을 수 있는 물고기가 없으면 엄마 호출 -> 반복문 끝
    if len(fishDist) == 0:
        break

    # 정렬된 리스트에서 값 하나 뽑아옴
    c, y, x = fishDist[0]

    # 정답에 거리 더해서 추가
    answer += c

    # 물고기 하나 먹었음 표시
    saveFish += 1
    # 지금까지 먹은 물고기가 아기 상어의 크기라면 아기 상어의 크기를 하나 올려주고 지금까지 먹은 물고기를 0으로 초기화한다.
    if saveFish == shark:
        shark += 1
        saveFish = 0

    # 물고기를 먹었다는 표시로 0
    graph[y][x] = 0
    # 상어가 물고기를 먹기 위해 움직인 위치
    startY = y
    startX = x
    # print(y, x, shark, answer)


print(answer)

여담

자바로 풀었으면 어땠을지 생각해봤다. 엄청... 코드가 길게 나왔을 듯.