[leetcode] 542. 01 Matrix

문제 : https://leetcode.com/problems/01-matrix/

---

0과 1로 이루어진 mat 배열이 주어질 때, 각 셸에서 0과 가장 가까운 거리를 저장한 배열을 만들어 반환하라.

---

BFS로 풀었다.

배열을 탐색하면서 0인 셸들의 x, y 좌표를 큐에 넣는다. 큐에 넣은 셸들의 0과 가장 가까운 거리는 0이다.

두 번 탐색하면 안되기 때문에 visit 배열을 만들고 큐에 넣은 좌표들의 visit을 true로 세팅한다.

큐를 탐색하며 큐의 front에 있는 좌표(let, (x, y))의 상하좌우 셸들 중에 탐색하지 않은 좌표(let, (nx, ny))들을 큐에 넣는다. 

그리고 큐에 넣은 좌표들의 탐색여부를 true로 갱신, 정답 배열의 값을 (x, y) 정답 배열의 값 + 1로 갱신한다.

 

mat의 크기를 N x M 이라 할 때, 시간/공간 복잡도는 O(NM).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/542.%2001%20Matrix.cpp