백준 화성지도 : 구간에 장벽을 세운다.

 백준 화성지도라는 문제는, 저를 골치 아프게 하던 문제 중 하나였습니다. 저는 이 문제를, 어떠한 상황으로 바꿔서 풀었습니다. 그 방법으로 접근해 보도록 하겠습니다. 세그 트리라는 말은 이 블로그에서는 언급하지 않았으니, '구간을 관리하는 자료 구조' 정도로 생각합시다. 그러면 조금 더 편하지 않을까 싶어요.

 

 

---

 문제를 보셨고, sweeping에 대한 개념이 어느 정도 쌓여 있다면, 다음과 같은 쿼리를 처리해야 한다는 것을 알 수 있습니다.

 

 문제의 특성상, 전체 구간을 보았을 때, 어떠한 특정 구간의 값이 0 미만으로 떨어질 일 또한 없다는 것을 알 수 있습니다. 구간 [a,b] 에 1이나 -1을 더하는 건 lazy 기법을 이용하면 쉽게 할 수 있을 듯 싶은데, 3번 쿼리가 문제입니다. 이 문제를 해결하기 위해, 장벽을 넣겠습니다. 장벽은 depth가 1 이상인 경우에 존재합니다.

 

 

 네모 칸들이 여러개가 있는데요. 여기서 밑에 부분 색깔이 하늘색이면 통과가 가능하고, 노란색이면 통과가 불가능합니다. 여기서 우리는 [a, b]에 장벽이 1겹 세워진다. 혹은 [a, b]에 장벽이 1겹 제거 된다는 쿼리가 들어왔을 때 어떻게 처리할 지 생각해 보도록 하겠습니다.

 

 예를 들어, a = 3, b = 6이라고 해 봅시다. 그러면, 실질적으로 접근하는 노드는 아래와 같습니다.

 

 

 여기서, 구간 [3, 6]에 장벽을 하나 세운다고 해 봅시다. 그러면, 노란색으로 칠한 부분은 통과 불가능한 '장벽'이 될 겁니다.

 

 

 여기서 d는 현재 노드에 세워져 있는 장벽이 d겹이다. 라는 것을 의미합니다. d > 0이라면, 이 노드의 장벽은 '막혀 있다'고 봐도 됩니다. v값이 문제인데요. 구간 [si - ei]를 표현하는 노드에 저장이 되어 있는 v값을 다음과 같이 정의해 봅시다.

 

 

 p가 [si-ei]라는 글이 써 있는 곳에서 출발을 하려고 합니다. 이 때, 말단인, si에서 ei까지 가는 것을 생각해 볼 수 있어요. 중간에 장벽으로 막혀 있으면 당연하게도 가지 못할 겁니다. 예를 들어, p는, ei로는 가지 못합니다. 중간에 장벽이 가로막고 있기 때문입니다. 저는 노드 [si-ei]의 v값을, [si - ei]라고 써져있는 지점에서부터, 말단 노드 si, si+1, ... , ei-1, ei까지 가는 것을 생각했을 때, 도달하지 못하는 말단 노드의 갯수로 정의해 보겠습니다.

 

 그러면 이 v값은 어떻게 구하면 좋을까요? 당연하게도 정의에 따르면, [si - ei]를 표현하는 노드 자체에 장벽이 세워진 경우, v값은 ei - si + 1입니다. 그렇지 않다면 어떻게 구해야 하나요?

 

 

 만약에 [si - ei] 노드에 장벽 4개가 모두 세워져 있지 않다면, 군청색으로 칠해진 왼쪽 자식과, 오른쪽 자식으로는 모두 갈 수 있을 겁니다. 왼쪽 자식의 v값을 le_value, 오른쪽 자식의 v값을 ri_value라고 해 봅시다. 이는, 각각 왼쪽 군청색으로 표시된 위치에서, 말단 노드까지 간다고 했을 때 도달할 수 없는 것의 갯수를, 오른쪽 군청색으로 표시된 위치에서 말단 노드까지 간다고 했을 때 도달할 수 없는 말단의 갯수를 의미합니다. 각각 0, 1입니다.

 

 따라서, [si - ei]라고 표시된 노드에 적어야 할 v값은 le_value에 ri_value를 더한 1이 됩니다.

 

 

 각 노드에 있는 v값이 이해가 되셨나요? 그리고 그것이 재귀적으로 왼쪽 자식의 v값과 오른쪽 자식의 v값의 합으로 정의된다는 사실도 이해 되셨나요? 그러면, 재귀적으로 부모를 타고 올라가면서 업데이트 해야 한다는 사실도 알 수 있겠네요.

 

 

 예를 들어, 구간 [4-5]를 표현하는 노드가 업데이트가 되었을 때, 추가로 업데이트 해야 하는 노드는 보라색으로 나타내었습니다. 군청색으로 표시된 것의 자식들이나, 군청색으로 칠한 것을 부모로 가지는 노드의 v값은 변하지 않습니다. 예를 들어 [6-7]이라는 구간에서 밑으로 내려갈 때, 노란색으로 칠해진 부분을 지나가지는 않습니다. [4-4]도 마찬가지입니다. 단지, 우리가 필요한 것은, [4-5]로 표시한 것과, 그것의 부모 노드들은 영향을 받을 수도 있었다는 것입니다. 즉, 군청색과 보라색 부분의 v값을 업데이트 해야 하는데요.

 

 이 보라색 부분은 자식을 업데이트 하고 나서, 부모를 업데이트 하는 식으로 대응하면 됩니다. 즉, [4-7]을 업데이트 할 때, [4-5]를 업데이트를 하고, [4-7]의 새로운 값을 구하기 위해서, [4-5], [6-7]의 v값을 가지고 옵니다.

 

 

 [4-7]을 업데이트 했다면 이제 무엇을 업데이트 하면 되나요? [0-7]을 업데이트 하면 됩니다. 이것은 [0-3]의 v값과, 새로 업데이트 된 [4-7]의 v값을 더하면 됩니다. 만약에, 이 상황에서 [4-7]에 장벽이 하나 새로 세워지면 어떻게 업데이트 해야 할까요?

 

 

 [4-7]이라고 표시된 노드의 v값을 4로 업데이트 하면 됩니다. [4-7]이라고 써져 있는 곳에 p를 세워놓는다고 합시다. 그리고, 노란색으로 표시된 위치는 통과를 못한다고 했을 때, [4-7]에서 말단 노드 4, 5, 6, 7까지 내려갈 수 없어요. 왜냐면 이미 [4-7]이 cover가 되었기 때문입니다.

 

 따라서, 생각할 필요도 없이, [4-7]을 담당하는 노드의 v값을 4로 업데이트 하고, depth를 하나 증가시킵니다. 그리고 보라색으로 표시한 [0-7] 노드를 업데이트 하면 됩니다. 정리하면 어떤 노드에 장벽을 세울 때, 그 노드의 depth 값은 하나 증가시키고, v값을 부모를 타고 올라가면서 갱신해 주면 됩니다.

 

 어렵지 않죠? 하나 주의해야 할 것은, 부모로 올라갈 때, depth가 1 이상인 경우, v값은 구간의 길이라는 것입니다.

 

---

 이제 장벽의 depth가 1에서 0으로 변하는 상황을 생각해 봅시다.

 

 

 그 이야기는 노드 자체에 완벽하게 쳐진 장벽이 사라진다는 이야기입니다. 이전에는 p가 군청색으로 칠해진 두 개의 자식 노드로 갈 수 없었습니다. 막혀 있었기 때문입니다. 그런데 장벽이 사라지면 군청색으로 칠해진 2개의 노드에 갈 수 있습니다.

 

 

 그러면 왼쪽 군청색에서 갈 수 없는 말단 노드의 수에다가, 오른쪽 군청색에서 갈 수 없는 말단 노드의 수를 더한 값을, [si - ei]를 표현하는 노드의 v값으로 취하면 될 거에요. 그리고, [si-ei]를 표현하는 노드가 변화했다면, 이들의 부모 값들도 변했다는 것을 의미합니다. 적절히 잘 처리해 주면 됩니다.

 

 단, 구간 [a - a]를 표현하는 노드의 경우 다르게 처리를 해 줘야 하는데요.

 

 

 예를 들어, [7-7] 노드에 있는 장벽이 제거된다고 해 봅시다. 그러면, 이 때에는 d값과 v값이 둘 다 0이 됩니다. 자식을 볼 필요도 없습니다. 그냥, 구간의 길이가 1이라면, 장벽이 있으면 1, 없으면 0입니다. 파란색으로 표시한 부분은 depth도 같이 업데이트 해야 하는 부분이에요.

 

 

 다음에 부모를 타고 올라가면서, 부모들의 v값을 업데이트 하면 됩니다. 당연하게도 보라색으로 표시한 노드들의 v값은, 그 노드들의 자식 둘의 v값의 합으로 업데이트 하면 됩니다.

 

 

 부모들을 업데이트 할 때 조심해야 하는 부분은 연두색으로 표시해 보았습니다. 제가 주구장창 설명한 내용을 코드로 구현하면 아래와 같습니다.

 

 

 먼저, depth[node_num]은, [node_s - node_e]로 표현되는 구간에 장벽이 몇 겹이나 세워져 있는지를 나타냅니다. 이는 크게 어려운 것이 없습니다. 그리고 update를 하고, upd를 하는데..

 

 

 만약에 해당 구간에 장벽이 세워져 있다면, 당연하게도 v의 값은 node_e - node_s + 1입니다. 그 값을 채워 넣고 빠져 나옵니다. 그렇지 않다면, node_s와 node_e가 같은 지를 보아야 하는데요. 같다면, 0을 넣습니다. 63번째 줄에 걸리는 경우, depth[node_num]이 0이기 때문입니다. 그렇지 않다면, 자식들의 v값을 끌고 와서 계산하면 됩니다.

 

 백준 화성 지도는, 값을 구하는 쿼리가 들어올 때, 전체에 대해서만 값 자체를  구하기 때문에, 이것만 고려해도 됩니다.

 

---

 이제 질문을 조금 바꿔보겠습니다.

 

 문제가 같은 것 같지만, 전체 구간에 대해서 구하는 것이랑, 일부 구간에 대해서 구하는 것이랑 차이가 좀 있습니다. 단순히 해당 노드에 속하는 구간들의 v값의 합으로 퉁칠 수 없기 때문입니다.

 

 

 예를 들어, [7-7]에 속하는 정수 i 중에 arr[i] > 0인 것의 갯수를 구해야 한다고 생각해 봅시다. [7-7]에서 밑으로 내려가는 방향은 막히지 않았기 때문에, v값은 0입니다. 그런데, 현재 0, 1, 4, 5, 6, 7이 켜져있다는 것을 알 수 있어요. 그러니, 구간 [7-7]에 속하면서 켜진 수는 0개가 아닌 7 하나라고 해야 하는데요.

 

 

 회색으로 표시된 부분의 부모는 [7-7] 구간을 포함합니다. 즉, [7-7]을 덮습니다. 이 부모들 중 하나 이상의 depth가 1 이상이라면, [7-7]의 v값과 상관없이, [7-7]구간에서 켜진 수의 갯수는 7-7+1개입니다. 만약에, 부모들이 모두 depth가 0이다. 그러면 v값을 취하면 됩니다. 이를 정리해 봅시다.

 

 

 만약에 구간 [si-ei]의 부모들 중 하나라도 depth 값이 1 이상이라면 구간 [si-ei]에서 arr[i] > 0인 것의 갯수는 ei - si + 1입니다. 그렇지 않다면, 밑 부분에서 arr[i] > 0인 가짓수를 구하면 되는데, 이는 노드 [si - ei]에 있는 v값이 들고 있습니다.

 

 

 그러므로, v값을 끌고 오면 됩니다. 구간이 겹치지 않는다면, 구간 내에서 계산된 결과를 리턴했을 때, 그 결과 값은 구간에 속한 정수의 갯수보다 크지 않습니다. 그런데, 방문하고 있는 각 노드에 대해서 부모 노드들을 모두 보면서, 부모 노드가 depth가 1이냐, 아니냐를 판단하려면, O(logn)만큼이 걸려요. 해당 노드에 대해서, 부모 노드의 depth가 1보다 큰 게 있는지 더 빠르게 판단하는 좋은 방법이 없을까요?

 

 

 depth가 1보다 큰, 구간을 관리하는 노드를 만났을 때 flag를 1로 설정합니다. B와 C를 호출할 때, 1이라는 flag 정보를 넘겨주면 됩니다. 만약에, depth가 0인 구간을 만나면 어떻게 하면 좋을까요? flag가 0이 넘어오면, 그냥 0을 넘기고, 1이 넘어온 경우에는 1을 넘기면 됩니다.

 

 3392번 화성지도는, 이것까지 고려할 필요는 없습니다. 화성 지도의 전체 코드는 링크에 있습니다.