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

문제 출처

[프로그래머스] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기

 

풀이

거리두기의 규칙이 정해지고 그 규칙에 지키지 않은 대기실은 0을 규칙을 잘 지킨 대기실은 1을 출력하여 5개의 대기실에 대해 배열을 반환하는 문제였습니다.

 

1. 대기실의 모든 영역을 돌아주면서(5 x 5 = 25) P를 찾아준다.

2. 현재 P를 기준으로 오른쪽 부분에 멘헤튼 거리를 지키지 않은 P가 존재하는지 확인한다. m값이 더 작은 P들은 검사해줄 필요가 없겠다는 생각이 들어 오른쪽 부분만 검사해주었다. 오른쪽 부분만 검사해주었다는 부분이 직관적이지 않게 들릴 수 있지만, 현재 n을 기준으로 n부터 시작해서 오른쪽 부분의 distance가 2가 넘지 않는 부분들을 검사해주었다.

3. 1번째 탐색 때는 빨간 원을 기준으로 주변을 검사해서 어떤 값을 가지고 있는지 반환해준다.

1번째 탐색

4. 1번째 탐색 값의 반환 값을 기준으로
P가 존재한다면 멘헤튼 거리가 지켜지지 않았기 때문에 지켜지지 않았다고 표시하고(flag = true)
P가 존재하지 않으면서 테이블인 경우 해당 테이블을 기준으로 도달할 수 있는 주변의 멘헤튼 거리에 P가 존재하는지 탐색하는 2번째 탐색을 돌려준다.

2번째 탐색

본인보다 m값이 더 적은 부분을 봐줄 필요가 없었기 때문에 다음과 같은 규칙을 발견하여 탐색해줄 수 있었다.

 

코드

GitHub - small-j/Algorithm