[Leetcode] 130. Surrounded Regions

문제 : https://leetcode.com/problems/surrounded-regions/

---

'X', 'O' 로 이루어진 m x n 배열이 있다. 'O'로 둘러쌓인 'X' 구역이 있다면 이들을 모두 'O'로 바꾸어라.

---

DFS, BFS 탐색으로 X로 이루어진 구역들을 구할 수 있다.

이 때, m x n 배열의 경계선에서부터 시작하는 X 구역들은 O로 둘러쌓인게 아니므로 범위에서 제외되어야 한다.

따라서 먼저 경계선에 존재하는 X 구역들을 모두 DFS나 BFS 탐색으로 이미 방문했다고 갱신한다.

이 후, 배열을 탐색하며 이미 방문/탐색 하지 않은 X구역들을 구한 뒤 이들을 모두 O로 바꿔주면 정답이 된다.

 

시간복잡도는 O(nm)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/130.%20Surrounded%20Regions.cpp