백준 16236 아기 상어 Python

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

문제 풀면서 어려웠던 점

1. 내가 풀면서 계산해본 답이 틀렸던 점 -> 분명 이해했다고 생각했는데 예제가 너무 커서 그런가 중간에 실수가 나왔던 것 같다.. 다행히 제대로 이해해서 풀었지만, 실전에서는 예제를 잘 풀어봐야 할 것 같다

2. if 조건을 제대로 적용하지 않은 점

   아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
   1.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
   2.먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
   3.먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
   3-1.거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
   3-2.거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

   위의 조건을 처음에는 1,2,3을 각각 독립된 것처럼 코드를 짰었다. 아래와 같이 했었는데.. 결과가 이상했다.

   if len(fish_list) >= 2:
       fish_list = sorted(fish_list, key=lambda x: x[2])
       if fish_list[0][2] == fish_list[1][2]: #거리가 가까운 물고기가 많다면, 오름차순 정렬했음에도 첫번째와 두번째의 거리가 같다면 그건 2개 이상인거니까..
           fish_list = sorted(fish_list, key=lambda x: x[0]) # 가장 위에 있는 물고기를 찾아줌

   당연하다. 첫번째 정렬 한 후 그 결과값을 저장했지만, 다시 기존의 거리가 가까운 조건은 무시한 채 다시 가장 위에있는 물고기를 찾았기 때문이다. 따라서 위 조건을들 동시에 충족하도록 정렬하는 것이 중요하다.

풀이

from collections import deque
n = int(input())

graph = []
queue = deque()

# 좌표 그래프를 입력받으면서 아기상어의 위치를 큐에 넣어주고(시작점), 그 시작점은 0으로 만들어서 진행에 방해물이 안되도록 만들어준다
for i in range(n):
    temp = list(map(int, input().split()))
    graph.append([])
    for j in range(n):
        graph[i].append(temp[j])
        if graph[i][j] == 9:
            queue.append((i,j, 0))
            graph[i][j] = 0

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 현재 상태에서 먹을 수 있는 물고기의 위치와 그 거리를 구하기
def get_fishes(cgraph, x, y, s_size):
    # 갔던 곳을 또 가면 그래프를 뱅뱅도니까 방문체크를 위한 visited 2차원 배열을 만들어준다
    visited = []
    for i in range(n):
        visited.append([])
        for j in range(n):
            visited[i].append(0)
    q = deque()
    q.append((x,y))
    visited[x][y] = 1
    fish_list = [] # 먹을 수 있는 물고기의 x,y좌표와 거리를 저장해둘 리스트
    shark_size = s_size # 상어의 크기에 따라 먹을 수 있는 물고기의 종류가 달라진다

    while q:
        cx, cy = q.popleft()
        if (cgraph[cx][cy] != 0) and (cgraph[cx][cy] < shark_size):
            # 0은 물고기가 없는 곳이니까 0이 아니면서 상어 크기보다 작은 물고기들을 먹을 수 있다
            fish_list.append([cx, cy, visited[cx][cy] -1])
            # visited check로 인해 시작점이 1이므로 표시한 값보다 -1한 값이 거리가 된다

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if nx >= n or ny >=n or nx <0 or ny <0: # 그래프 경계
                continue
            if cgraph[nx][ny] > shark_size: # 사이즈보다 큰경우 지나갈 수 없음
                continue
            if visited[nx][ny] == 0:
                q.append((nx, ny))
                visited[nx][ny] = visited[cx][cy] + 1

    return fish_list

# 큐에는 다음으로 가야할 곳을 저장해두는 용도
sec = 0
shark_size = 2
confirm = 0
while queue:
    eat = 0 # 상어가 먹은 물고기 수, 물고기의 크기가 변할때마다 다시 세야하므로 안에서 초기화해줌
    # if confirm == 10:
    #     break
    #print("shark_size", shark_size, eat)

    while eat < shark_size: # 상어의 사이즈 마다 먹을 수 있는 물고기의 수가 정해진다 최대로 크기만큼만 물고기를 먹을 수 있고, 0부터 시작하므로 <
        cx, cy, csec = queue.popleft() # 현재 x,y와 xy좌표까지 오는데 걸리는 시간
        sec = sec + csec # 전체 시간에 계속 더해줌
        graph[cx][cy] = 0 # 방문처리
        fish_list = get_fishes(graph, cx, cy, shark_size) # 먹을 수 있는 물고기 리스트를 구함

        if len(fish_list) >= 2: # 먹을 수 있는 물고기가 1마리보다 많다면
            # x[2] 가장 가까운 거리 순,
            # x[0] 가까운 물고기가 많다면 행이 작은 순
            # x[1] 그래도 많다면 열이 작은 순
            fish_list = sorted(fish_list, key=lambda x: (x[2], x[0], x[1])) # ★이 정렬로 다 풀었다고 해도 과언이 아니다 !
            queue.append(fish_list[0]) # 그때의 첫번째 값이 다음 목적지가 된다
        elif len(fish_list) == 1: #1마리라면 그 물고기를 먹을 감
            queue.append(fish_list[0])
        elif len(fish_list) == 0: # 먹을 수 있는 물고기가 없다면 도움요청, 반복을 멈춘다
            break
        eat += 1

    shark_size =shark_size + 1 # 음식을 최대한으로 다 먹으면, 사이즈가 커지니까 +1해줌


print(sec)