[백준] 아기상어 [풀이 해설 + 코드 + 시간복잡도를 계산해보자?]

구현 & 시뮬레이션 & BFS

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

코드

import sys
from collections import deque
input = sys.stdin.readline


n = int(input())

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


dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
sX, sY = 0, 0
for i in range(n):
	for j in range(n):
		if arr[i][j] == 9:
			sX,sY = i, j
			break


def bfs(s, e, arr, shark, dx):	

	queue = deque([[s, e]])
	visited = [[0] * n for _ in range(n)]
	distance = [[0] * n for _ in range(n)]

	visited[s][e], distance[s][e] = 1, 1


	fish = []
	while queue:
		x, y = queue.popleft()

		for idx in range(4):
			nx = dx[idx][0] + x
			ny = dx[idx][1] + y

			if 0<= nx < n and 0<= ny < n and visited[nx][ny] == 0:

				if arr[nx][ny] > shark: 
					continue
				else:
					
					queue.append([nx, ny])
					visited[nx][ny] = 1
					distance[nx][ny] = distance[x][y] + 1
					
					if 0 < arr[nx][ny] < shark:	
						fish.append([distance[nx][ny]-1, nx, ny])

	if fish:
		fish.sort(key = lambda x : (-x[0], -x[1], -x[2]))
	return fish


eat, shark, total = 0, 2, 0
while True:
	result = bfs(sX,sY, arr, shark, dx)

	if not result: break

	distance, fx, fy = result.pop()
		

	arr[sX][sY], arr[fx][fy] = 0, 0

	eat += 1
	if eat == shark:
		shark += 1
		eat = 0
        
	sX, sY = fx, fy
	total += distance

print(total)

 

설명

 해당 문제의 코드는 다른 블로그에 포스트 하신 분들과 별 차이가 없을 것이라 생각하여 코드를 보기 보다 어떤 흐름을 가지고 생각을 해봤었는지를 보시면 좋을 것 같습니다 :) (물론 제대로 풀지도 못했습니다만..) 알고리즘을 공부하면서 들었던 생각을 정리해보고자 하는 게 포스팅의 목적이니 이를 중점적으로 생각해 주시고 봐주시면 감사하겠습니다.

 

 이번 문제는 비용이 존재하지 않은 최단 거리를 구하는 문제 유형이다. 처음 문제를 읽었을 때 주어진 조건대로 구현하면 된다고 생각하여 막상 시도를 해봤지만 생각처럼 제대로 논리가 이어지지 않았다. 그 이유는 다음과 같다.

 

 

먹을 수 있는 상어를 어떻게 찾을 것인가.

먹을 수 있는 상어를 찾았을 때 어떻게 해야 할 것인가.

이동은 어떻게 해야 하는 것인가.

상어가 먹을 수 있는 곳으로 갔을 때 크기가 변경되는 시점은 어떻게 해야 하는 것인가.

이동거리는 어떻게 계산해야 하는 것인가.

 

 

 위 조건들을 살펴보면 해당 문제의 가장 핵심적인 부분들을 담당하고 있는 것이라고 볼 수 있다. 그중에서 가장 생각하기에 힘들었고 결국 풀어내지 못했던 주요 원인이 바로 3번째 생각이었다. ' 상어가 먹을 수 있는 곳으로 갔을 때 크기가 변경되는 시점은 어떻게 해야 하는 것인가.' 문제에서는 먹을 수 있는 곳은 상어가 현재 가지고 있는 크기보다 작은 경우의 물고기만 먹을 수 있다. 따라서 이는 곧 크거나 같은 크기를 가진 물고기는 먹을 수 없다는 걸 의미한다. 그렇다면 상어가 먹을 수 있는 곳으로 이동을 했을 때 이동과 동시에 물고기를 먹는다고 문제에서 명시했기 때문에 먹고 난 뒤에 크기가 변한다. 그럼 크기가 변했기 때문에 먹을 수 있는 물고기가 달라진다. 혹은 추가되게 될 수 있다. 예를 들어 현재 크기가 3이라고 했을 때 한 번만 더 먹으면 크기가 증가하게 된다. 그렇다면 한 마리의 물고기를 더 먹고 나서 크기가 변했을 때 상어의 현재 크기는 4가 된다. 그럼 이전에는 2인 크기만 먹을 수 있었다. 왜냐하면 상어의 현재 크기는 3이기 때문에 자기보다 작은 크기의 물고기를 먹으려면 3은 안되고 2, 1 만 가능하기 때문이다. (0에 관해서는 이후에 설명한다.) 다시 돌아와서 크기가 4가 되었을 때는 그럼 먹을 수 있는 물고기가 달라지기에 먹을 수 있는 물고기를 다시 찾아야 한다. 근데 bfs를 실행하는 도중에 다시 찾게 된다면 해당 현재 위치에서 찾게 되는 게 아니기 때문에 문제에서는 상어의 현재위치에서 거리가 가장 작은 최소를 찾게 명시해 두었다. 따라서 크기가 4가 되었다는 건 해당 구역의 물고기를 먹었던 것이고 상어의 위치가 변경되었기 때문에 ' 변경된 위치에서 찾는 ' 것은 문제 구현상 위배된다. 그렇기 때문에 크기가 변했을 때 먹을 수 있는 물고기를 어떻게 찾아야 할지 굉장히 막막했다. 이전에 풀었던 문제들은 전부 한 번의 BFS만으로 모든 문제를 해결했기 때문이다... 그럼 다음 원인을 살펴보자.

 

 ' 이동 거리는 어떻게 계산해야 하는 것인가. ' 이도 참 어려웠다. 거리가 최소가 되는 지점은 BFS를 진행하게 되면 최적의 경로를 보장하니 도착지점까지는 최적의 경로를 보장하게 된다. 근데 여기서 참 생각이 꼬였던 것은 그럼 먹을 수 있는 물고기들이 있는 곳을 목적지로 하여 BFS를 따로 수행해야 되는 건가? 지금 생각해 보면 BFS가 최단 경로를 보장한다고 생각했음에도 불구하고 그 목적지까지 다시 설정하여 BFS를 돌리게 한다는 건 멍청한 생각이었다. 결국 먹을 수 있는 곳은 도착가능한 지점이 되고 그 도착 가능한 지점에 대해서 항상 최적의 경로를 보장한다는 걸 다시 돌려서 또 생각한 것이다. 이 또한 문제를 풀지 못했던 주요 원인이 되었다. 나머지  두 개의 원인은 큰 문제가 되지 않았다. 다만 위에 두 원인들 때문에 결국 끝내 풀어내지는 못했지만 다시 풀어보면서 생각을 되뇌며 풀어본 결과 아직 생각대로 구현이 잘 되지 않는다는 게 느껴지게 해 준 큰 문제다. 이제부터는 풀이를 보면서 어떤 생각을 했는지 적어 보려고 한다.

 

 문제에서 요구하는 목적 자체는 ' 아기 상어가 엄마한테 도움을 요청하지 않고 스스로 물고기를 먹을 때까지의 시간 '이다. 이는 곧 아기 상어가 엄마한테 도움을 요청한다는 건 문제에서 명시를 해두었는데 ' 먹을 수 있는 물고기가 공간에 없는 경우다. ' 따라서 현재 크기보다 큰 물고기들 만 남거나, 물고기가 없는 경우는 먹을 수 있는 물고기가 공간에 없다가 된다. 따라서 이 조건을 break 시점으로 두고 생각해 본다면 종료 조건도 찾았다는 걸 알 수 있다. 다음으로 상어를 어떻게 찾을 가이다. 상어가 이동할 수 있는 조건은 상하좌우 인접한 칸을 이동한다. 하지만 자기보다 큰 물고기가 있는 칸은 지나갈 수 없기 때문에 자기보다 작거나 같은 구간에 있는 물고기가 있는 칸만을 지나간다. 시뮬레이션 로직을 통해서 현재 상어가 가지고 있는 크기보다 작거나 같은 구간을 찾아가며 이동을 하게 되고 이러한 이동 시점은 항상 최적의 경로를 보장하게 된다. 그렇다면 문제에서 상어가 이동할 수 있는 조건들을 명시해 두었기 때문에 그 조건들을 가지고 상어들을 찾으면 되는 것이다. 그럼 우선 현재 크기보다 작은 상어들을 찾고 이후에 지금까지 찾아온 물고기들은 상어가 먹을 수 있는 물고기를 의미하기 때문에 그 물고기가 한 마리라면 그 한 마리는 그냥 먹으면 된다. 하지만 그렇게 찾은 물고기가 여러 마리라면, 1마리 이상이라면 조건이 존재한다. 거리가 가장 최소가 되는걸 기준으로 하며, 거리가 최소가 되는 지점들이 여러 개일 때 가장 위에 즉 x좌표상으로 가장 위에 있는 것들을 먼저 먹고, 그러한 물고기들이 여러 개라면 가장 왼쪽 즉 y좌표상으로 가장 왼쪽에 있는 물고기를 먹게 된다. 따라서 현재 크기에서 먹을 수 있는 물고기들을 찾고 그 물고기들이 여러 마리인지 혹은 한 마리 이은 지에 따라 어떤 물고기를 먹는지가 달라지게 되며, 그렇게 선택된 물고기를 먹었을 때 크기가 바뀌게 되는지 혹은 바뀌지 않는지가 결정이 된다. 그럼 이는 상어가 이동했을 때 크기가 변경되었을 때 고려해야 되는 문제를 해결하게 된 것이다. 왜냐하면 먹을 수 있는 물고기들을 찾고 난 다음 조건에 맞는 물고기를 먼저 먹으러 가기 때문에 그러한 물고기가 골라졌을 때 그 물고기를 먹고 나서 다시 BFS를 통해 먹을 수 있는 물고기를 찾으면 되기 때문이다. 여기서 BFS가 여러 번 사용될 수 있음을 알 수 있었고 BFS가 여러 번 사용될 수 있는 이유는 문제의 목적상 먹을 수 있는 물고기가 변경되며, 또한 물고기를 먹고 변경된 상어의 위치에서의 이동거리가 달라지기 때문에 해당 위치에서 (상어가 존재하는 위치에서) 다시 BFS를 수행해야 되기 때문이다. 이러면 모든 문제의 원인들을 해결할 수 있다. 이어서 그 물고기를 먹고 난 이후에 행동들을 해주면 되며, 이때 주의해야 할 점은 현재 크기만큼 물고기를 먹었을 때 크기는 증가하고 먹었던 횟수를 초기화시켜주지 않으면 값이 제대로 나오지 않게 된다. 왜냐하면 2마리를 먹었을 때 3이 되고 3마리를 먹었을 때 4가 되는 시점이기 때문에 먹은 횟수가 되었을 때 1씩 증가하게 되기 때문에 이어서 먹게 되는 게 아니다. 만약 이렇게 하지 않는다면 3마리를 먹었을 때 크기가 4가 되면 이후에 BFS를 통해 한 마리를 먹었을 때 4가 되기 때문에 크기는 지속적으로 증가하게 된다. 이는 예제를 돌려보며 확인해 볼 수 있다. 또한 주의 해야 되는건 0이다 0은 빈칸이며 물고기가 아니다. 물고기가 가질 수 있는 크기는 1~6까지다 따라서 현재 상어가 가지고 있는 크기보다 작은거에 0은 포함이 되면 안된다는 것이다. 그리고 먹고나서 이전 상어의 위치를 변경 해주어야 한다. 왜냐하면 상어는 이동했기 때문이고 이동 했으니 이전 위치는 물고기도 아닌 빈칸으로 남겨지기 때문이다.

 

 구현의 조건대로 구현을 했을 때 BFS에서 이전에 풀어봤던 경로를 저장하는 방법을 사용했다는 걸 볼 수 있다. 그 지점까지 가는 경로가 항상 최적의 경로를 보장하기 때문에 해당 경로가 얼마큼 시간이 걸렸는지 혹은 얼마큼 지나왔는지는 상어가 1초마다 이동이 가능하기 때문에 1초를 가지고 블록의 개수로 적용해 본다면 블록이 지나온 개수는 곧 상어가 먹을 수 있는 물고기가 있는 곳까지 간 시간이 된다. 문제에서 몇 초 동안 엄마상어의 도움을 요청하지 않고 먹을 수 있는지 구하라고 하기 때문에 결국 먹을 수 있는 물고기가 없을 때까지 몇 초 동안 먹게 되었냐를 의미한다. 따라서 상어가 먹을 수 있는 물고기의 위치 까지들의 합이 엄마 상어의 도움 없이 스스로 먹게 되는 시간들인 것이다.

 

 추가적으로 시간복잡도를 계산을 좀 해보면 BFS의 시간복잡도가 공간의 모든 정점을 탐색하는 시간들이니까 O(N^2) 만큼의 시간이 걸린다. 거기에다가 + E (간선의 개수) 만큼 더해지게 되는데 간선의 개수는 한 정점당 4개의 간선을 가지고 있어 O(4 * N^2)의 시간을 가지며 BFS가 한 번만 진행하는 게 아닌 먹을 수 있는 공간으로 이동할 때마다 BFS를 수행해야 되기 때문에 추가적으로 O(4 * N^2)만큼의 시간이 더 들게 된다. 그리고 한 번의 BFS를 돌 때마다 정렬을 수행해 주는 로직 때문에 O(nlogn)만큼의 시간복잡도를 더 가지게 되어 대략 80 정도의 시간이 추가된다. 이를 전부 계산해 봤을 때 약 80만 400 정도의 시간이 나오게 되며 c언어를 기준으로 1초에  1억 번 연산이 가능하다는 걸 생각하고 상대적으로 시간복잡도가 느린 python을 고려했을 때 1초에 약 3천만 번을 계산하는 파이썬 같은 경우 대략 2.13초 정도 걸리게 된다. 문제에서 제한시간으로 2초를 요구하고 있으며 이를 조금이라도 줄여보고자 fish가 있을 때만 정렬을 수행하며 fish가 없을 때는 정렬하지 않는다. 결과적으로 192ms -> 188ms로 4ms차이지만 약간의 논리를 추가로 인해 시간복잡도를 줄였다고 볼 수 있다.