백준 16236 아기상어 파이썬 풀이

난이도 : 골드3

풀이일 : 04274

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

16236번: 아기 상어

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

문제 요약

1. 상어는 본인 크기보다 작은 물고기만 먹음
2. 상어 크기와 같은 수의 물고기 먹으면 성장
3. 상어와 크기 같은 물고기 칸 통과 가능, 섭취 불가능
4. 먹을 수 있는 물고기가 많다면 거리가 가까운 물고기 섭취
    거리가 가까운 물고기가 많다면 위, 왼쪽 우선순위
5. 아기상어 최초 크기 2, 좌표 9, 물고기 크기 1~6

---

1차 시도 오답 -> 시간 초과

import sys
from collections import deque

def distance(arr, food):
    global total, count, shark
    idxi = 0
    idxj = 0
    second = n * n
    for w in range(len(food)//2):
        queue = deque([food[w*2], food[w*2+1]])   
        visited = [[0] * n for _ in range(n)]  
        while queue:
            i = queue.popleft()
            j = queue.popleft()
            di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
            for k in range(4):
                ni, nj = i + di[k], j + dj[k]
                if 0 <= ni < n and 0 <= nj < n and visited[ni][nj] == 0:
                    if arr[ni][nj] == 9:   
                        if visited[i][j] + 1 < second:
                            second = visited[i][j] + 1
                            idxi, idxj = food[w*2], food[w*2+1]
                        continue
                    elif arr[ni][nj] <= shark:   
                        visited[ni][nj] = visited[i][j] + 1
                        queue.append(ni)
                        queue.append(nj)
    if second != n*n:
        for x in range(n):
            for y in range(n):
                if arr[x][y] == 9: 
                    arr[x][y] = 0
        arr[idxi][idxj] = 9
        total += second       
        count += 1            
        if count == shark:  
            shark += 1
            count = 0
    else:
        arr[idxi][idxj] = 0   
    return

n = int(sys.stdin.readline())
sea = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

shark = 2
total = 0
count = 0

while True:   
    food = deque([])
    for a in range(n):
        for b in range(n):
            if 0 < sea[a][b] < 7 and sea[a][b] < shark:
                food.append(a)
                food.append(b)
    if food:
        distance(sea, food)
    else:
        break

print(total)

 

이전에 풀었던 코드에 deque 적용해봤는데도 오답

무슨 짓을 해도 시간초과가 나와서 한 달 전에 낙담했었다

풀이를 떠올리는 과정보다 오늘 통과한 코드를 메모하는 게 좋을 것 같아서 생략

---

최종 정답

# 최초 상어 좌표 찾은 후 find 함수 실행

# find 함수
# BFS 탐색으로 거리 기록
# 먹을 수 있는 물고기 발견 시 시간 기록, deque 삽입
# 최소거리 초과시 조사 중단, 물고기 i, j 좌표 우선 정렬
# 물고기 먹고 상어 위치 재할당
# 먹은 물고기 수, 상어 크기 등 고려 후 반복

import sys
from collections import deque

def find(x, y, fish):
    global shark
    visited = [[0] * n for _ in range(n)]
    load = deque([x, y])
    visited[x][y] = 1
    while load:
        i = load.popleft()
        j = load.popleft()
        if fish and fish[0][0] < visited[i][j]:    # 최소 거리 초과 시 조사 중단
            continue
        di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
        for k in range(4):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < n and 0 <= nj < n and visited[ni][nj] == 0:
                if sea[ni][nj] <= shark:  # 상어와 같으면 이동 가능
                    visited[ni][nj] = visited[i][j] + 1
                    load.append(ni)
                    load.append(nj)
                    if 0 < sea[ni][nj] < 7 and sea[ni][nj] < shark: # 먹이 발견 시 시간, 좌표 기록
                        fish.append([visited[i][j], ni, nj])
    return fish.sort()

n = int(sys.stdin.readline().strip())
sea = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
shark = 2
sec = 0    # 총 이동 시간
eat = 0    # 먹은 물고기

x = y = 0    # 상어찾기
for a in range(n):
    for b in range(n):
        if sea[a][b] == 9:
            sea[a][b] = 0
            x, y = a, b

while True:
    food = []    # 먹이 물고기 담을 배열
    find(x, y, food)

    if food:    # 문제 조건에 따라 맨 앞 물고기 먹음
        sec += food[0][0]
        x, y = food[0][1], food[0][2]
        sea[x][y] = 0
        eat += 1
        if eat == shark:    # 상어 성장 확인
            eat = 0
            shark += 1
    else:    # 먹을 물고기가 없다면 반복 중단
        break

print(sec)

코드 구성

1. 최초 상어 좌표 찾은 후 find 함수 실행

   상어의 좌표에 해당하는 값 0 재할당 후 진행
2. find 함수

    BFS 탐색으로 거리 기록 -> deque 사용으로 시간초과 방지
    먹을 수 있는 물고기 발견 시, [시간, i, j] 리스트에 추가
    최소거리 초과시 조사 중단, 물고기 i, j 좌표 우선 정렬
3. 먹을 물고기가 있다면 먹고, 상어 위치 재할당

    먹은 물고기 수와 상어 크기 비교후 상어 성장 확인
4. 먹을 물고기가 없을 때까지 반복

---

느낀점

처음에는 먹을 수 있는 물고기를 리스트에 담아 방문 가능 여부를 확인하려고 했었는데,

지금은 큰 물고기가 가로막고 있어 못먹지만 향후 상어가 크면 먹을 수도 있는 물고기 처리가 불가능해 방향 변경

 

한 달 전에는 이틀 간 고민하고 실패했는데 지금은 풀어내서 기분 좋다!