[BFS] 백준 16236 아기상어

문제링크 www.acmicpc.net/problem/16236

 

본인보다 크기가 작고 거리가 작으며, 가장 위에 있는 혹은 가장 왼쪽에 있는 물고기를 먹는 문제이다

조건이 많아 까다로웠다

 

 

[답코드]

 

1. 처음 구현

import sys
from heapq import heappop, heappush
from collections import deque
input=sys.stdin.readline

def dfs():
    # 거리를 알기 위한 완전탐색
    m = deque()  # 움직일 좌표를 담아두는 m
    m.append([0, shark[0], shark[1]])
    visit = [[False] * n for _ in range(n)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    visit[shark[0]][shark[1]] = True
    while m:
        dist, row, col = m.popleft()
        for i in range(4):
            next_r = row + move[i][0]
            next_c = col + move[i][1]
            if 0 <= next_r < n and 0 <= next_c < n and not visit[next_r][next_c] and graph[next_r][next_c] <= size:  # 그래프 범위 안
                if 0 < graph[next_r][next_c] < size:  # 먹을 수 있는 물고기들 담음
                    heappush(q, [dist + 1, next_r, next_c])
                # 크기가 같으면
                visit[next_r][next_c] = True
                m.append([dist + 1, next_r, next_c])

n=int(input())
graph=[list(map(int, input().split())) for _ in range(n)]

# 아기상어가 있는 위치
shark=[]
for i in range(n):
    for j in range(n):
        if graph[i][j]==9:
            shark.append(i)
            shark.append(j)
            graph[i][j]=0
size = 2
q = []  # 먹을 수 있는 물고기들을 담아두는 q(거리, row, col)
cnt=0
feed=0
while True:
    dfs() #먹을 수 있는 물고기들을 담아온다
    if len(q)==0:
        break
    #가장 거리가 짧고 위에, 왼쪽에 있는 물고기 먹음
    dist, r, c = heappop(q)
    cnt+=dist
    shark[0], shark[1]=r, c
    graph[r][c]=0
    feed+=1
    q=[]
    if feed==size:
        size+=1
        feed=0
print(cnt)

처음에는 BFS의 거리에 대해 깊게 이해하지 못해

아기상어의 크기가 5이면 아기상어보다 크기가 작은 물고기들은 거리가 1이든, 2이든, 3이든 상관없이 모든 물고기의 위치를 담아왔다(비효율적)

 

 

2. 시간 복잡도, 공간복잡도가 작아진 구현

import sys
from heapq import heappop, heappush
input=sys.stdin.readline

n=int(input())
graph=[list(map(int, input().split())) for _ in range(n)]
q = []  # 거리, row, col
for i in range(n):
    for j in range(n):
        if graph[i][j]==9:
            heappush(q, [0, i, j])
            graph[i][j]=0
            break
size = 2
cnt=0
feed=0
visit = [[False] * n for _ in range(n)]
while q:
    d, r, c = heappop(q)

    if 0<graph[r][c]<size: #사이즈가 작으면 잡아 먹는다
        feed+=1
        if feed==size:
            size+=1
            feed=0
        cnt+=d
        d=0
        graph[r][c]=0
        if len(q)!=0:
            q=[]
        visit = [[False] * n for _ in range(n)]
    for dr, dc in [-1, 0], [1, 0], [0, -1], [0, 1]: #사방 탐색
        next_r = r + dr
        next_c = c + dc
        if 0 <= next_r < n and 0 <= next_c < n and not visit[next_r][next_c] and graph[next_r][
            next_c] <= size:  # 그래프 범위 안, 아기상어보다 작으면
            heappush(q, [d + 1, next_r, next_c])
            visit[next_r][next_c] = True

print(cnt)

BFS 탐색을 진행하면 어차피 길이가 1인 노드들이 모두 나가면 길이가 2인 노드가 모두 q에 쌓여있게 된다.

이 떄문에 같은 거리의 아기상어의 크기보다 작은 물고기들은 q 안에서 모두 정렬되게 된다

 

 

 

해당 개념을 유의하며 문제를 풀면 시간 단축이 가능해진다