BOJ16236 아기 상어

문제

BOJ16236 아기 상어
골드IV | 백준 16236 | Python3 파이썬 풀이

삼성 SW 역량 테스트 기출 문제이다.

알고리즘

구현 + 시뮬레이션 문제이다. 직접 아기 상어를 움직여가며 결과를 확인해야 한다.
또한 BFS를 이용해 다음 먹이를 찾는다.

매 스텝마다 아기 상어는 물고기 한 마리를 잡아 먹는다. 우선순위는 다음과 같다.
1. 자신의 크기보다 작은 물고기를 먹을 수 있다.
2. 먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹는다.
3. 최단 거리에 있는 물고기가 여러 마리라면 가장 왼쪽에 있는 물고기를 먹는다.

또한, 아기 상어는 상하좌우로 움직이며, 한 칸을 이동할 때 1초가 걸린다.
단, 아기 상어는 빈 칸 혹은 자신의 크기보다 작거나 크기가 같은 물고기가 있는 칸은 지날 수 있다.

즉, BFS는 같은 레벨 단위(여기서는 거리가 같은 칸들)로 탐색하므로 BFS를 이용해 먹을 수 있는 물고기를 전부 찾은 후 거리, x좌표가 왼쪽인 순서로 정렬해 당장 먹을 물고기를 선택한다.

아기 상어의 크기는 처음 2부터 시작한다. 또한, 먹은 물고기 수와 자신의 크기가 같다면 크기가 1 증가한다.

아기 상어가 더 이상 먹을 수 있는 물고기가 없다면 종료하고, 총 소요 시간을 출력한다.
DP 문제들에서처럼 선택할 수 있는 변수가 전혀 없기에 위 우선순위 그대로 구현하고 시뮬레이션만 하면 된다. (최단 거리 물고기가 여러 마리인데 선택하라고 했다면 정말 어려워졌을 것이다)

코드에 대한 자세한 설명은 아래 코드에 주석을 달아놓았다.

코드

import sys
from collections import deque

input = sys.stdin.readline
move = [[-1, 0], [0, -1], [0, 1], [1, 0]]

# BFS - 먹을 물고기 찾기
def BFS(currx, curry):
    queue = deque()
    queue.append([currx, curry])
	
    # 맵의 칸 방문 여부
    visited = [[False] * N for _ in range(N)]
    dist = [[0] * N for _ in range(N)] # 시작점부터 각 칸까지 거리
    visited[currx][curry] = True 
    eat = [] # 먹을 수 있는 물고기 리스트

    while queue:
        currx, curry = queue.popleft()

        for i in range(4):
            nextx = currx + move[i][0]
            nexty = curry + move[i][1]
			
            # 맵에서 벗어나지 않고, 방문하지 않은 곳이라면
            if 0 <= nextx < N and 0 <= nexty < N and (not visited[nextx][nexty]):
            	# 상어 크기와 같거나 작은 물고기거나, 빈 칸이면 지나갈 수 있다
                if sea[nextx][nexty] <= sharksize or sea[nextx][nexty] == 0:
                    visited[nextx][nexty] = True
                    dist[nextx][nexty] = dist[currx][curry] + 1
                    # 다음 위치 탐색
                    queue.append([nextx, nexty])
                
                # 먹을 수 있는 물고기라면 (상어 크기보다 작다면)
                if 0 < sea[nextx][nexty] < sharksize:
                    eat.append([nextx, nexty, dist[nextx][nexty]])
	
    # 먹을 수 있는 물고기 리스트가 비어있다면
    if not eat:
        return -1, -1, -1
    
    # 거리, x좌표, y좌표순으로 정렬 (x좌표는 작을수록 왼쪽)
    eat.sort(key=lambda x : (x[2], x[0], x[1]))
    # 가장 가까운 1순위 물고기 정보 반환
    return eat[0]


N = int(input())
sea = [list(map(int, input().split())) for _ in range(N)]
time = 0 # 소요 시간
sharksize = 2 # 아기 상어의 크기

for i in range(N):
    for j in range(N):
        if sea[i][j] == 9: 
        	# 아기 상어의 위치를 따로 저장
            sharkpos = [i, j]
            sea[i][j] = 0
            break

# 먹은 물고기의 수
eatcount = 0
while True:
    # BFS를 이용해 먹을 물고기의 위치와 거리를 찾는다
    eatx, eaty, distance = BFS(*sharkpos)
	
    # 더 이상 먹을 수 있는 물고기가 없다면 종료
    if eatx == -1:
        break
    
    # 물고기를 먹기 위해 이동
    sharkpos = [eatx, eaty]
    # 물고기를 먹었으니 맵에서 삭제
    sea[eatx][eaty] = 0
    # 먹은 물고기 수 증가
    eatcount += 1
	
    # 먹은 물고기 수와 상어 크기가 같아졌다면
    if eatcount == sharksize:
    	# 아기 상어 크기 1 증가
        sharksize += 1
        eatcount = 0
	
    # 이동한 거리만큼 소요 시간 증가
    time += distance

print(time)

결과

solved.ac 난이도 기여