[BOJ] 16236번 아기 상어 / 사용언어 : 파이썬(python)

※ 문제링크 

16236번: 아기 상어

해당문제는 BFS를 활용하여 풀 수 있는 문제였다. 여러가지 상황을 고려하여 구현을 해야했기에 풀이에 대한 방향성과 방법을 떠올리는 것보다 실제 구현이 더 오래 걸린 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다.

1. 완전탐색을 통해 아기상어의 위치, 아기 상어가 먹을 수 있는 먹이의 개수와 좌표값을 구하고 저장한다.

2. 상어가 각 좌표로 이동할 수 있을때, 해당 좌표까지 이동하는데 걸리는 시간을 측정할 BFS함수로 구한다.

3. 문제 조건에 맞게 아기 상어가 먹게하고, 반복문을 통해 아기상어가 자신의 크기만큼 먹이를 먹으면 크기를 갱신한다.

4. 아기상어가 먹이를 먹을 때마다 그 시간을 저장하고, 더 이상 먹을 수 없으면 결과값을 출력한다.

 

def bfs(x, y):
    queue = deque()
    queue.append([x, y])
    visited[y][x] = 0
    cnt = 0

    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < N:
                    if visited[ny][nx] == -1 and sea[ny][nx] <= shark_size:
                        visited[ny][nx] = cnt + 1
                        queue.append([nx, ny])
        cnt += 1

import sys
from collections import deque

# input = sys.stdin.readline
N = int(input())
sea = []
for _ in range(N):
    sea.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0 , -1, 1]
cp = True
ans = 0
shark_size = 2

while cp:
    upgrade_check = 0
    ce_list = []
    for x in range(N):
        for y in range(N):
            if 0 < sea[y][x] < shark_size:
                ce_list.append([x, y, -1])
            if sea[y][x] == 9:
                shark_loc = [x, y]
                sea[y][x] = 0

    for _ in range(shark_size):
        if cp:
            visited = [[-1 for _ in range(N)] for _ in range(N)]
            bfs(shark_loc[0], shark_loc[1])
            value = [float('inf') for _ in range(3)]

            # 조건에 맞는 먹이를 찾는 반복문
            for i in range(len(ce_list)):
                x, y = map(int, ce_list[i][:2])
                time = visited[y][x]
                ce_list[i][2] = time
                if time != -1: # 해당먹이로 이동할 수 있는지 확인 -1이면 이동 불가하다는 뜻
                    if time < value[2]: # 먹이의 거리가 기존의 먹이보다 작을 경우 해당 먹이로 대체
                        value = ce_list[i] 
                        check = i
                    if time == value[2]:
                        if ce_list[i][1] < value[1]: # 먹이의 거리가 기존 먹이와 같지만 기존먹이보다 상단에 있을 경우 대체
                            value = ce_list[i]
                            check = i
                        # 먹이의 거리가 기존 먹이와 같고 y값도 같지만 기존 먹이보다 좌측에 있으면 대체
                        if ce_list[i][1] == value[1] and ce_list[i][0] < value[0]:
                            value = ce_list[i]
                            check = i
            if value != [float('inf') for _ in range(3)]:
                shark_loc = [value[0], value[1]]
                sea[shark_loc[1]][shark_loc[0]] = 0
                ans += value[2]
                upgrade_check += 1
                ce_list.pop(check)
            else:
                cp = False
    if shark_size == upgrade_check:
        shark_size += 1
print(ans)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.