bounding box를 이용해서 가희와 거북이 인형을 풀어봅시다.

 가희와 거북이 인형은 그리 어렵지 않아 보이는 bfs, dfs입니다. 그런데, 거북이 컴포넌트가 최대 10^6-1개까지 올 수 있어서, 자칫하다가는 시간초과가 날 수 있습니다. 그래서, 1달 전에 여행가면서 예약했던 글에는 상대 속도의 개념을 이용하자는 내용이 있었습니다.

 

[관련글]

상대 속도를 응용한 문제들을 풀어 봅시다.

 

---

 그런데, 제가 설명을 누락한 부분이 있는데, 바로 bounding box 부분입니다. 예제를 가지고 설명해 보겠습니다. 우리는 거북이의 맨 위에, 맨 위에 있다면 가장 좌측에 있는 이 부분을 기준 좌표로 가지고 돌렸습니다.

 

 

 거북이 컴포넌트들이 처음에 이 위치에 있다고 해 보겠습니다. 이 상태에서 오른쪽으로 거북이가 이동할 수 있을까요?

 

 

 아닙니다. 이동하면, 컴포넌트 하나가 맵 바깥을 벗어나기 때문입니다. 그러면 아래로 이동시키는 것은 될까요?

 

 

 아뇨. 그것도 안 됩니다. 이번에는 밑에 있는 컴포넌트가 맵 바깥으로 나갔습니다. 이 거북이를 이루는 요소들을 bounding box로 묶을 수 있습니다.

 

 

 요렇게요. 그러면 이 bounding box가 오른쪽으로 1칸 이동하거나 아래로 1칸 이동할 수 있나요? 아닙니다. 바깥으로 나가면 맵에서 벗어나 버리기 때문입니다. 22337번 문제에서는 이 점까지 고려했는지 보고자 문제를 냈습니다.

 

---

 그러면, 이런 경우는 어떨까요?

 

 거북이 컴포넌트들이 요래 있어요. 그러면 제일 위에 있는 것이 1행에 있는 것 중 하나입니다. 1행에 있는 것들 중에, 기준점을 잡습니다. 저는 제일 왼쪽에 있는 것을 잡겠습니다.

 

 

 그러면 요렇게 잡힐 겁니다. 주황색은 기준점입니다. 즉, 1행 3열이 기준점일 때, 컴포넌트들은 위 그림과 같이 있게 됩니다.

 

 

 bounding box로 떨궈버리면 위와 같아요. 그러면 거북이 컴포넌트들이 이동할 수 있는지는, 이 bbox가 맵을 벗어나지 않고 이동할 수 있는지 물어보는 문제로 바뀌게 됩니다. 사실, 이 bbox를 만드는 규칙은 발견하셨을 지도 모르겠지만, 최서단, 최동단, 최북단, 최남단 이렇게 4개를 가지고 만든다는 것을 알 수 있겠네요.

 

 

 이들을 모두 포함하는, 축에 평행한 box. AABB하고 비슷하긴 합니다.

 

---

 먼저, 컴포넌트들로부터 bbox를 만듭니다. 이 부분은 2중 for loop로 하고 있습니다. 그리고 turtle에 넣는 순서를 보셔야 하는데요. 위에서 아래로, 좌측에서 우측으로 보기 때문에, turtle[0]에 들어간 것은 맨 위에 있는 요소, 맨 위에 여러 개가 있다면 제일 왼쪽에 있는 것을 뽑아오게 됩니다.

 

 이 기준 좌표를 (tx, ty)라 합시다. 그러면 (tx, ty)일 때 bbox의 범위를 구할 수 있습니다. 이를 토대로 뭘 할 수 있을까요? 우리는 기준 좌표가 특정 위치에 있을 때, bbox가 어느 범위에 있는지 알았습니다. 그러면 기준 좌표가 x 방향으로 dx, y 방향으로 dy만큼 변했을 때, bounding box도 x 방향으로 dx만큼, y 방향으로 dy만큼 이동했을 겁니다.

 

 예를 들어, 윗 방향으로 0칸, 왼쪽 방향으로 1칸 이동하면 bounding box도 왼쪽 방향으로 1칸 이동해요. 그러면, 기준 좌표가 특정 좌표에 올 수 있는지 없는지는, bbox를 움직여 보면서, bbox가 맵 안에 속하는지만 보면 될 겁니다. 이를 체크하는 코드는 아래와 같습니다.

 

 

 이것까지 적용한 최종 풀이는 여기에서 보실 수 있습니다.