문제 풀이
잠깐만요
문제 풀이 경험이 있다면 ‘이 문제는 너비 우선 탐색(BFS)으로 풀어야 하는 거 아닌가요?’라고 문의할 수 있습니다. 그러나 문제의 총 크기가 5x5이기 때문에 BFS로 풀지 않아도 충분하며, 이번에는 일부러 사용하지 않고 배열 접근으로만 풀어보겠습니다(문제를 보는 시각을 키우기 위해서는 여러 방법으로 풀어보는 것이 중요합니다). 어렵고 비효율적으로 보이더라도 한번 작동 원리를 이해하고 나면 나중에 배울 DFS, BFS 개념을 이해할 때 도움이 많이 될 것입니다.
먼저 참고 사항에 있는 맨해튼 거리에 대해 다시 설명하면 ‘두 점 간의 거리는 두 점의 좌표 차이를 절댓값의 합으로 표현하는 방식’입니다. 쉽게 말해 두 점 간의 거리가 2 이상 차이나야 거리두기를 실천한 것이라고 말할 수 있습니다. 문제를 풀 때는 거리두기를 실천한 것을 찾기보다 거리두기를 실천하지 않은 것을 찾는 게 더 빠르므로, 맨해튼 거리가 2 이하인 경우만 확인하는 방식으로 문제를 풀겠습니다. 단 거리만 측정하는 것이 아니라 파티션의 존재도 고려해야 하기 때문에 추가적인 검증이 필요합니다.