본문 바로가기
  • Floodnut's Home Directory
프로그래밍/알고리즘

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

by Floodnut 2022. 5. 10.
 

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

[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1]

programmers.co.kr

 

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

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

 

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

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

 

 

위와 같은 그림을 보자.

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

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

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

 

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

 

 

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

알고리즘 풀이 모음. Contribute to Floodnut/algorithm development by creating an account on GitHub.

github.com

 

'프로그래밍 > 알고리즘' 카테고리의 다른 글

[백준] 2252 - 줄 세우기  (0) 2022.06.01
프로그래머스 - 거리두기 확인하기  (0) 2022.05.10
[백준] 2178 - 미로 탐색  (0) 2022.04.27
[백준] 1987 - 알파벳  (0) 2022.04.13
[백준] 2606 - 바이러스  (0) 2022.04.11
프로그래머스 - 더 맵게(42626)  (1) 2022.04.01

댓글0