백준 원판 돌리기 : deque를 사용하면 쉽다.

 오늘은 다소 빡센 구현 문제를 다뤄보도록 하겠습니다. 백준의 원판 돌리기 문제는 읽어 보셨을 겁니다. 혹시나, 안 읽어보셨다면, 링크로 가셔서 읽어보세요. 생각보다 문제가 깁니다. 중요한 조건은, 원판도 50개 이하, 적혀있는 수도 50개 이하, 회전 연산의 횟수도 50회 이하라는 것입니다.

 

 그러면 1칸씩 회전을 한다고 해도 2500^2, 그리고 원판에서 적절한 연산을 하는 후처리는 연산당 50^3이 걸리겠네요.

 

 

---

 일단, 문제를 3개로 쪼개는 것이 필요합니다.

 

 이렇게 쪼갰다면, (1)번부터 차근차근 보도록 하겠습니다.

 

 

 일렬로 편다는 것이 무슨 말인지 이해가 안 가실 듯 싶은데요. 쉽게 생각해 보겠습니다.

 

 

 원판에 수가 위와 같이 적혀 있다고 해 보겠습니다. 시계 방향으로 1칸 회전시키면 어떻게 될까요?

 

 

 요렇게 됩니다. 이것을 일렬로 보겠습니다. 12시부터 시계 방향으로 읽겠습니다.

 

 

 맨 뒤에 있는 거를 뺍니다.

 

 

 다음에 그것을 맨 앞에 넣습니다. 그러면 시계 방향으로 회전한 것이 처리가 됩니다. 반시계는 어떻게 하면 될까요?

 

 

 반시계로 돌렸다면 위와 같을 겁니다.

 

 

 원판을 일렬로 편 배열에서 맨 앞에 있는 것을 뺍니다.

 

 

 그것을 맨 뒤로 옮깁니다. 맨 앞과, 맨 뒤에서 원소를 삽입, 삭제 연산을 효율적으로 하는 자료구조는 deque입니다.

 

 

 제가 설명한 것을 그대로 코드로 구현하면 위와 같습니다.

 

 

---

 (2)번은 어떻게 하면 좋을까요?

 

 그 위치에 있는 수가 제거된 수라면 건너 뜁니다. 그렇지 않으면, 상하좌우 인접해 있는 노드들을 검사해서, 그 중에 하나라도, '그 위치'에 있는 수와 같으면 제거하면 됩니다.

 

 

 다만, 좌우 인접을 조심할 필요가 있는데요. 원판 하나를 일렬로 폈을 때, 배열의 가장 오른쪽에 있는 수와, 가장 왼쪽에 있는 수는 인접하므로, 그에 대한 처리를 하셔야 합니다.

 

 4방향을 돌면서 체크를 하는 함수는 chk입니다.

 

 

 다음에, 지워야 할 수면 visit에 1을 mark 해 줍니다.

 

 

 지우고 난 후에는 inf로 업데이트 합니다. 이전에 지워졌던 수라면, 이미 dq[i][j]가 inf입니다. 따라서, 이 때에는 count를 하지 않습니다. 최종적으로, 지워진 수의 갯수는 be개입니다. be의 값이 0이 아니면 여기서 끝내면 됩니다.

 

 

---

 지워지지 않은 수가 하나도 없다면 어떻게 하면 좋을까요?

 

 평균 계산을 하시면 됩니다. 총 합계에 변량 갯수를 나눈 값이 평균입니다. 실수 계산은 귀찮으니, 정수 계산으로 바꿔보겠습니다. 평균에 지워지지 않은 수의 갯수를 곱한 게 총 합계가 됩니다. 어떤 수에 지워지지 않은 수의 갯수를 곱한 값을 가지고 판단해 주시면 됩니다.

 

 회전을 시킨다. 인접한 수들을 제거해 본다. 그렇지 않으면 average를 구한다. 3개의 기능으로 쪼개면 다소 어렵지만 무난하게 해결을 할 수 있습니다.