[BOJ] 백준 2468. 안전 영역

▶문제설명

[BOJ] 백준 2468. 안전 영역

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

▶Hint

---

BFS/DFS 문제이다.

1. NxN 배열에 높이 정보를 입력받으면서 가장 높은 값과 낮은 값을 구한다.

2. 1에서 구한 가장 낮은 값부터 가장 높은 값까지 모든 경우에 대하여

NxN배열의 모든 인덱스에 대해 안전 영역을 구하는 BFS를 수행하며 

BFS를 수행한 횟수를 카운트하면서 카운트 값의 최대 값을 구한다.

인접한 안전 영역을 체크하는 BFS를 수행하여 visited배열에 안전 영역을 true값으로 저장하고

visited[i][j]==false인 경우에만 BFS를 수행하도록 구현한다.

▶시간 복잡도

---

최악의 경우 O(N^6) 만에 정답을 구할 수 있다. 

N = 100, 최소 높이 = 1, 최고 높이 = 100인 경우

100 개의 모두 다른 높이 값으로

100X100개의 모든 인덱스에 대해서 BFS를 수행하게 된다.

대략 최대 1,000,000번의 연산이므로 1초 내에 해결이 가능하다!

▶Solution