[BOJ] C++ 2573 빙산 - BFS, 시간 복잡도 잘 계산하기

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 예제 5 7 0 0 0 0 0 0 0 0 2 4 5 3 0 0 0 3 0 2 5 2 0 0 7 6 2 4 0 0 0 0 0 0 0 0 0 ans : 2 가장 먼저 떠올릴 수 있는 풀이는 1년 후 빙산의 형태로 바꾸고 바꿀 때마다 BFS를 돌리는 방법이다. 이 방식으로 했을 때 구현은 쉬워 보이지만 시간 복잡도가 문제가 된다. 위의 방식대로 시간 복잡도를 계산해 보자. 최대 300 * 300 크기의 배열에 빙산이 높이 10까지 있을 수 있다. 300 * 30..

2023.10.17