백준 16236 : 아기상어

문제 링크

유명한 삼성 SW 기출 문제다.

bfs 아이디어 자체는 어렵지 않지만, 제약 조건을 잘 읽고 이해해야 디버깅하는 시간을 크게 줄일 수 있다.

특히 놓치지 말아야할 제약 조건

1. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

2. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.

처음에 1을 고려하지 않았다가 하나하나 과정을 트래킹하면서 잘못된 부분을 찾을 수 밖에 없었다..

## 기본적인 bfs 준비 및 시작점 지정
import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
graph = []
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip().split())))

for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            start_row = i
            start_col = j
            break
            
def bfs(i,j, size, move, eat_count):
    dx = [-1,0,0,1]
    dy = [0,-1,1,0]
    dq = deque()
    next_dq = deque()
    
    # 먹이 후보에 넣을 때 시간순으로 정렬될 수 있도록 1초씩 이동할 때마다 시간을 기록
    depth = 0 
    candidate = []
    
    graph[i][j] = 0
    dq.append((i,j))
    
    while dq:
        x,y = dq.popleft()
        if 0 < graph[x][y] < size:
            candidate.append((depth,x,y))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] > size:
                continue
            if move[nx][ny] > 0:
                continue
                
            move[nx][ny] = move[x][y] + 1 
            next_dq.append((nx,ny))
            
        if len(dq) == 0:
            dq = next_dq
            next_dq = deque()
            depth += 1
            
    if len(candidate) > 0:
    	# depth, 행, 열 순서로 정렬했지만, 우선순위 큐를 쓸 수 있다면 편할 것 같다
        candidate.sort(key=lambda x: (x[0],x[1],x[2]))
        
       	# 가장 빠른 시간에 먹을 수 있고, 제일 위, 제일 오른쪽에 있는 물고기의 위치로 가서 먹기
        next_x = candidate[0][1]
        next_y = candidate[0][2]
        graph[next_x][next_y] = 0
        eat_count -= 1
        # 다음 시작점, 다음 시작점까지 가는데 걸린 시간, 성장까지 카운트다운 기록 리턴
        return [next_x,next_y, move[next_x][next_y], eat_count]
        
    #아무것도 못 먹을 경우
    return [None,None,None,None]
    
size = eat = 2
total_time = 0

while True:
    move = [[0]* n for _ in range(n)]
    x,y, time, eat_count = bfs(start_row,start_col,size,move,eat)
    # 더 이상 먹을 게 없을 경우 반복문 종료
    if x == None:
        break
        
    total_time += time
    start_row, start_col = x,y
    # 사이즈 업 가능할 경우
    if eat_count == 0:
        size += 1
        eat = size
    else:
        eat = eat_count

print(total_time)

BFS을 일단 구현해놓고 덕지덕지 디버깅을 하다보니 비효율적인 코드들이 좀 보인다. 리턴 타입 언패킹 때문에 [None,None,None,None]을 썼다든가.. 먹이 후보 리스트(candidate)를 우선순위 큐를 안 쓰고 정렬을 썼는데, 어차피 dq가 빌 때까지 bfs를 돌린다면 dq를 next_dq로 갈아치우는 과정은 굳이 필요한 단계는 아닐 것 같다(그럼 depth 관리는 어떻게 해야하지...?!).