[백준] 16236번 : 아기 상어 - 파이썬

아이디어 : 구현, BFS, 자주쓰는 함수 정의

BFS 기반 알고리즘 문제로, 

아기 상어와 가까운 곳부터 지나갈 수 있는 길을 탐색한다.

 

이때, 일반적인 BFS 와 다르게

지나갈 수 있는 길에 아기 상어가 먹을 수 있는 후보 물고기가 있는 경우

"가장 위쪽->왼쪽" 물고리를 먹고, 다시 BFS 알고리즘을 사용해야한다.

 

따라서, 임시 자료구조에 같은 Level(거리)의 원소를 모아서 특정 로직을 수행한 뒤, Queue에 후보 path를 넣어야한다.

* 특정 로직 : 후보 물고기가 있는 지 & 있다면 물고기 선택 등

 

즉, Queue안에는 항상 같은 Level(거리)의 원소만 존재하게된다.

 

문제 해결 과정

1. 초기 아기 상어 위치를 queue 자료구조에 put 한다.

2. 4방위 탐색으로 후보 물고기 & path 찾는다.

    - queue.empty() 까지 아래 로직 반복한다.

    - queue.get()하여 4방위 탐색한다.

    - 지나갈 수 있는 길 (<= shark_size) 을 fish_path_list 자료구조에 넣는다.

    - is_fish : 지나갈 수 있는 길에 물고기가 있는 경우 True

    - check_graph : 이미 탐색한 길은 제외하기 위해 체크한다.

3-1. is_fish == True 인 경우

    - get_closest_fish() : 가장 위/왼쪽에 있는 물고기를 찾는다.

    - eat() : 물고기를 먹고 성장한다.

3-2. is_fish == False 인 경우

    - fish_path_list 의 원소를 queue에 넣는다.

4. 종료 조건 확인

    - queue 가 비었으면 더 이상 진행할 수 없음을 의미

    - 결과값 리턴 (총 탐색 횟수 - 마지막 탐색 횟수)

5. 2~4 번로직을 반복한다.

나의 답안

import sys
import queue

input = sys.stdin.readline

N = int(input().strip())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

sy = 0
sx = 0

for y in range(N):
    for x in range(N):
        if graph[y][x] == 9:
            sy = y
            sx = x
            graph[y][x]=0

dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]


def get_closest_fish(fish_path_list, shark_size):
    for fish in fish_path_list:
        fy, fx = fish
        if graph[fy][fx] != 0 and graph[fy][fx] != shark_size:
            break

    for fish in fish_path_list:
        ty, tx = fish
        if graph[ty][tx] != 0 and graph[ty][tx] != shark_size:
            if fy >= ty:
                if fy > ty:
                    fy = ty
                    fx = tx
                else:
                    if fx > tx:
                        fy = ty
                        fx = tx
    return fy, fx

def eat(size, eatting):
    eatting = eatting + 1
    if eatting == size :
        size = size + 1
        eatting = 0
    return size, eatting

def check_path():
    return True

def bfs(y,x):
    # shark path
    que = queue.Queue()
    que.put((y,x))
    result = 0
    sub_result = 0
    check_graph = [[0 for _ in range(N)] for _ in range(N)]
    shark_size = 2
    shark_eatting = 0

    while 1:
        # 초기값
        is_fish = False
        fish_path_list = []
        result = result + 1
        sub_result = sub_result + 1

        # 4방위 탐색으로 후보 물고기 & path 찾기
        while not que.empty():
            qy, qx = que.get()
            for i in range(4):
                y = qy + dy[i]
                x = qx + dx[i]
                if 0 <= y < N and 0 <= x < N:
                    if check_graph[y][x] != -1:
                        if graph[y][x] <= shark_size:
                            fish_path_list.append((y,x))
                            if graph[y][x] != 0 and graph[y][x] != shark_size:
                                is_fish = True
                            else:
                                check_graph[y][x] = -1
        
        # 먹을 수 있는 물고기 있는 경우 / 없는 경우
        if is_fish :
            # print("## EAT ##")
            # 가까운 물고기 탐색
            fy, fx = get_closest_fish(fish_path_list, shark_size)
            # 먹기
            shark_size, shark_eatting = eat(shark_size, shark_eatting)
            graph[fy][fx] = 0
            # clear path
            check_graph = [[0 for _ in range(N)] for _ in range(N)]
            sub_result = 0
            que.put((fy,fx))
        else:
            for fish in fish_path_list:
                que.put(fish)

        # 종료 조건 - 피쉬 혹은 경로가 없는 경우
        if que.qsize() == 0 :
            return result - sub_result

    return result - sub_result

print(bfs(sy,sx))

 

주의 1 - 크기가 같은 물고기가 있는 칸은 지나갈 수 있고, 먹을 수 없다 !

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고,
나머지 칸은 모두 지나갈 수 있다.

아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

 

주의 2 - 아기 상어는 가까운 물고기 중 "가장 위쪽->가장 왼쪽" 물고기를 먹어야한다 !

def get_closest_fish(fish_path_list, shark_size):

    for fish in fish_path_list:
        fy, fx = fish
        if graph[fy][fx] != 0 and graph[fy][fx] != shark_size:
            break

    for fish in fish_path_list:
        ty, tx = fish
        if graph[ty][tx] != 0 and graph[ty][tx] != shark_size:
            if fy >= ty:
                if fy > ty:
                    fy = ty
                    fx = tx
                else:
                    if fx > tx:
                        fy = ty
                        fx = tx
    return fy, fx

fish_path_list 에는 "지나갈 수 있는 길"과 "먹을 수 있는 물고기" 가 함께 존재한다.

 

따라서 먹을 수 있는 물고기인지 확인하고,

"가장 위쪽->가장 왼쪽" 위치인지 확인해야 한다.