문제 풀이

이 문제에서는 단순히 상하좌우를 확인하는 것이 아니라 맨해튼 거리가 2인 모든 위치를 확인해야 합니다. 하지만 걱정하지 마세요. 앞서 배운 dx, dy를 잘 응용하면 맨해튼 거리가 2인 모든 위치도 무리 없이 표현해낼 수 있습니다.

우선 거리두기를 어떻게 검사할 것인지 생각해봅시다. 맨해튼 거리 2 내에 파티션이 사이에 있지 않은 다른 응시자가 있는지 검사해야 합니다. 우리가 주목할 점은 맨해튼 거리 2에 도달하려면 먼저 맨해튼 거리 1을 거쳐야 한다는 것입니다. 그리고 맨해튼 거리 1은 바로 상하좌우죠.

▲ 그림 3-16 맨해튼 거리 1과 맨해튼 거리 2

즉, 맨해튼 거리 2인 위치에 도달하려면 맨해튼 거리 1인 위치를 거쳐야 하고, 맨해튼 거리 1의 위치들이 파티션으로 막혀 있다면 맨해튼 거리 2에는 다른 응시자가 있어도 파티션에 가로막히기 때문에 거리두기가 인정됩니다.