[프로그래머스] Python - 거리두기 확인하기

코딩테스트 연습 - 거리두기 확인하기

 

프로그래머스 레벨2 문제로 카카오 인턴십 코딩테스트 출제 문제다.

주어진 리스트에서 사람들이 거리두기를 지키는지 확인하면 된다.

 

이 문제의 경우 BFS-FloodFill로 해결할 수 있었다. 

탐색 범위가 제한되어 한 번의 탐색 자체는 빠르나 방문 판정을 내리지 않고 중복으로 확인해야하는 경우가 있었다.

 

 

위와 같은 그림을 보자.

P는 사람, X는 칸 막이, 초록색은 기준, 파란색은 거리두기를 지키는 사람, 노란색은 거리두기를 지키지 않는 사람이다.

초록색 P의 위치에서 맨해튼 거리(x 거리 + y 거리) 안의 노란색 P는 칸 막이 없이 거리두기를 지키지 않는다.

반대로 파란색 P들은 맨해튼 거리 2 안에 있지만 칸 막이를 통해 거리두기를 지킨다.

 

이를 BFS로 구현하여 이동한 거리가 2를 초과하거나 X를 만난다면 continue, 그 전에 노란색 P를 만난다면 바로 0을 반환하게 하였다.

 

GitHub - Floodnut/algorithm: 알고리즘 풀이 모음