백준 16768 : 뿌요뿌요 게임을 구현해 봅시다.

 왠지 오늘은 뿌요뿌요 게임을 구현해 보고 싶어졌습니다. 구현 문제로, 고전 게임들을 구현하라는 문제가 생각보다 많이 나오는데요. 뿌요뿌요 역시 구현력을 보기 위한 좋은 문제 중 하나입니다. 문제는 아래와 같습니다.

 

 16768번 문제를 단순화 시키면 위와 같습니다. 일단, 이 문제가 구현력으로 cover가 되는지, 아니면 optimize를 해야 하는지, 아니면, 특수한 알고리즘을 써서 시간 복잡도 자체를 낮춰야 하는지부터 보도록 하겠습니다.

 

---

 먼저 문제를 간단하게 분석해 보도록 하겠습니다.

 

 

 먼저 칸의 수는 최대 1000개입니다. 그러면 각 칸이 하나씩 연쇄적으로 없어진다고 했을 때, 1000 연쇄까지 일어날 수 있을 거에요. 정말 극단적으로 생각했을 때요. 그러면, 1연쇄가 일어날 때 어떤 일이 일어날까요? 없어져야 할 블록들을 탐색해야 하고, 그 블록들을 제거합니다.

 

 그렇게 하려면, O(wh) 만큼의 복잡도가 필요합니다. 높이는 최대 100이고, 너비는 10입니다. 그렇기 때문에, 1000 연쇄 x 1000칸 = 10^6입니다. 적절히 잘 구현을 해도 된다는 것을 알 수 있어요. 그러면, 어떤 기능부터 구현해야 할 지 천천히 생각해 봅시다.

 

 

 먼저, work 함수를 구현해 봅시다. 이것은 제거해야 할 블록들을 찾아내서 marking 하는 역할만 합니다. 다음에 upd 함수를 구현할 건데요. 이것은, 제거가 될 블록들을 제거하고, 맵을 업데이트 하는 역할을 합니다. 이 2개의 함수만 잘 구현하면, 답을 출력하는 것 정도는 어렵지 않게 해결할 수 있습니다.

 

 

 work 함수를 봅시다. 먼저 visit 함수를 초기화 해 줍니다. 이것은 해당 칸을 방문했는지를 나타냅니다. 10n개의 칸을 돌면서 볼 건데요. str[i][j]의 값이 '0'이거나, 이미 i행 j열을 방문했다면, 건너 뜁니다. 그렇지 않다면, 어떤 일을 해야 할까요? 위치 (i, j)부터 탐색을 시작해야 할 겁니다.

 

 이 부분부터 보도록 하겠습니다.

 

---

 블록이 이런 식으로 있다고 생각해 봅시다. 현재 (i,j)부터 탐색을 할 거에요. 상, 하, 좌, 우로 인접해 있다면, 벡터 4개는 다음과 같이 저장을 하면 좋을 겁니다. dir = {(-1,0), (1,0), (0,-1), (0,1)}. 이를 토대로 현재 위치와 그와 인접한 위치들을 모두 검사하면 됩니다. 그런데, 보시면 (i,j)의 색깔이 보라색인데요. (i, j-1)을 탐색할 필요가 있을까요? 없습니다. 왜냐면 색이 다르기 때문입니다.

 

 그렇기 때문에, 탐색을 시작할 때, 시작점의 색깔도 저장해 놓습니다.

 

 

 73번째 줄에서, ch를 저장하고 있다는 것을 알 수 있어요. 이는 기준점의 색깔입니다. 만약에 탐색하고 있는 위치에 있는 색깔이 ch와 같다면, 그것을 Queue에 넣고, 그렇지 않다면, 넣지 않으면 됩니다. 이 처리는 81번째 줄의 if문과 83번째 줄의 if문에서 처리하고 있습니다.

 

 이렇게 한다면, Queue에서 빠진 item의 수가 (x,y)와 연결이 된 요소의 원소 갯수 정도로 이해하시면 됩니다. 이것을 v에다가 모두 넣고 있고요. v는 bfs가 호출이 될 때 마다 clear가 되고 있어요.

 

 

 81, 83번째 줄을 보시면, 81번째 줄은 범위를 넘어가거나, 이미 방문했다면 더 이상 탐색하지 않아요. 인접한 영역이 시작 위치와 색깔이 달라도 탐색하지 않는데요. 이는 83번째 줄의 if문에서 처리하고 있습니다.

 

 

 만약에 v의 크기가 k보다 작다면, 무시해도 됩니다. k개의 요소가 이어져 있을 때 제거하라고 했기 때문입니다. 그렇지 않다면, 제거를 해야 한다는 marking을 해야 하는데요. 제거해야 할 블록을 (x, y)라고 한다면, str[x][y] = '0', 그러니까 빈 공간으로 두어도 문제가 없습니다.

 

 예를 들어서, K = 3이고, 아래와 같은 데이터가 있었다고 해 봅시다.

 

 

 여기서 흰색으로 칠해진, 0이 쓰여진 블록은 빈 공간이라고 해 봅시다. 그리고 K = 4라고 해 봅시다. 쉽게 말해, 뿌요뿌요의 규칙을 따른다는 의미입니다. 이 경우, 제거되어야 하는 block들은 없습니다.

 

 

 이 때에는 노란색 부분만 제거하면 됩니다. 이 경우, 노란색 부분을 0으로 바꿔주면 됩니다.

 

 

 이 경우에, work는 5를 리턴하고, 맵은 위와 같이 바뀝니다.

 

 

---

 이 때, 블록들이 내려오는 것도 고려해야 합니다. 떠 있는 block들은 없으니까요. 열별로 나눠서 보면 될 듯 싶습니다.

 

 

 이렇게요. 그러면, 떠 있는 블록들을 어떻게 내리면 좋을까요? 임시 배열을 선언한 다음에 내려도 좋겠습니다만. 더 좋은 방법이 있습니다. 포인터를 2개 두겠습니다. i와 po입니다. 밑에서 부터 보기 때문에 각 열별로 수행했을 때, 처음에 i와 po는 h번째 행을 가리킵니다.

 

 

 더 정확히 말하면 현재, c번째 열을 보고 있다면, i와 po는 str[h번째 행][c번째 열]에 있는 값을 가리키고 있습니다. 그림으로 간략하게 도식화를 하면 위 그림과 같고요. 이 때, i가 가리키는 값이 0이라면, i만 감소합니다.

 

 

 그런데, i가 가리키는 값이 0이 아니라면 어떻게 하면 좋을까요? po가 가리키는 값을 i가 가리키는 값으로 갱신하면 됩니다. 그리고 i와 po를 이동시키면 됩니다.

 

 

 그러니까, 이렇게 po가 가리키는 위치에 1을 집어넣습니다.

 

 

 그리고 i와 po 포인터를 이동시킵니다. 다음에 보니까, i가 가리키는 값이 0입니다. 이 경우에는 i만 감소를 할 텐데요.

 

 

 이동을 시켰더니, 끝에 도달했습니다. 그러면, po 위치에서부터 맨 위에 행까지 0으로 채워주면 되겠죠.

 

 

 이것을 1열, 2열, ... , 10열에 대해서 반복 수행해 주시면 됩니다.

 

 

 제가 설명한 것을 코드로 구현하면 위와 같습니다. 2개의 함수만 구현했을 뿐인데, 뿌요뿌요를 구현했네요. 중요한 소스만 대략적으로 블로그에 올렸습니다. 이 패턴은 퍼즐 게임을 구현하라는 구현 문제에서 많이 쓰이는 패턴입니다. 외우시지는 마시고, 이렇게 나누면 좋겠거니. 정도만 생각하셔도 괜찮겠네요. 전체 코드는 여기에서 보실 수 있어요.