[programmers][2021카카오인턴십] 거리두기 확인하기

문제 : https://programmers.co.kr/learn/courses/30/lessons/81302

---

BFS로 풀었다.

하나의 대기실을 탐색하면서 people 좌표를 찾으면 BFS를 돌린다.

탐색하면서 테이블을 만나면 계속 탐색, 파티션을 만나면 탐색 중지, 또다른  people을 만나면 거리두기 실패임을 알 수 있다.

만일 탐색하면서 3이상의 거리가 된다면 거리두기를 성공적으로 하고 있으므로 BFS 탐색을 중지해도 된다.

 

시간복잡도는 하나의 people 좌표에서 BFS를 돌리는데 people 좌표 탐색 O(NM). 한 번의 BFS 탐색시 O(NM)이 소요되므로 총 O((NM)^2). 하지만 거리두기 2 이상은 탐색할 필요가 없으므로 BFS 탐색 시간복잡도는 상하좌우 4방향으로 2번만 탐색하면 되니까 최대 4^2 = 16, 상수 시간복잡도를 가진다고도 볼 수 있다.

따라서 O(NM)으로 봐도 무방하다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/2021%20%EC%B9%B4%EC%B9%B4%EC%98%A4%20%EC%B1%84%EC%9A%A9%EC%97%B0%EA%B3%84%ED%98%95%20%EC%9D%B8%ED%84%B4%EC%8B%AD/%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0%20%ED%99%95%EC%9D%B8%ED%95%98%EA%B8%B0.cpp