[백준 19235] 모노미노도미노 (C++)

A. 문제설명

www.acmicpc.net/problem/19235

19235번: 모노미노도미노

문제에 대한 자세한 설명은 링크 참조

 

1. 아래와 같은 빨간/파란/초록색 보드가 붙어있는 형태의 배열판이 존재

2. 그리고 게임에서는 아래와 같은 형태의 1*1, 2*1, 1*2 크기의 블록을 사용

3. 게임의 규칙은 1번의 그림과 같이 빨간색에 먼저 블록이 배치되고, 해당 도형이 테트리스의 규칙과 같이 파란/초록색 영역으로 우선 이동

4. 도형은 빨간색 영역에 배치된 모양을 유지하여 횡/축으로 각각 이동

5. 테트리스의 규칙과 같이, 초록색 영역은 한 행이 전부 도형으로 가득차면 해당 줄을 없애고, 파란색 영역은 한 열이 가득차면 없앰

6. 5번에 따라 열/행의 도형들이 제거되면, 위에 있는 도형들은 아래로 쏟아짐

7. 이후 도형들이 쏟아졌는데 다시 테트리스가 발생할 수 있다면 5번부터 반복

8. 테트리스 검사를 마친 후, 초록/파란색 각각의 영역에서 연한부분(0,1행/열)내 도형이 있는지 검사

9. 여기서, 해당 칸에 도형이 존재시, 있는 영역의 크기만큼 원래의 도형들을 내려주어야 함

10. 이 과정을 매 도형이 빨간색 영역이 들어올 때마다 반복하며, 1회의 테트리스가 1점을 준다고 가정할 때 최종으로 구해지는 점수와 초록/파란색 영역내 남은 도형의 갯수를 구하라

 

B. 접근법

시뮬레이션

 

제목은 모노미노 도미노이지만 실제로는 테트리스 게임의 구현이라고 보면 된다. 일단 문제에서 요구하는 조건들이 많아 크게 몇가지로 정리해보았다.

 

1. 블록의 입력, 그리고 파란/초록색 영역으로의 이동(내려가기)

내 코드의 경우, put_block()가 해당 구현에 해당하는데, 여기서 빨간색 영역의 배열을 따로 사용해주지 않았다. 어차피 초록/파란색 영역의 연한부분으로 이동할 것이기 때문에 해당 부분으로 바로 이동해주었다.

그리고 도형이 1*2, 2*1인 경우에 각각 초록/파란색 영역에 따라 도형의 일부가 걸리는 경우에 대한 예외처리를 하여 일부가 중간 블록에 걸리면 이동을 멈추도록 구현하였다.

 

2. 테트리스 확인, 한 줄이 블록으로 가득 찬 경우 해당 열/행 제거 + 점수 추가

내 코드의 170라인의 아래 코드가 해당 내용에 해당한다.

while(tetris_blue()){ push_block_blue(); }
while(tetris_green()){ push_block_green(); }

 

3. 테트리스 후, 없어진 열/행에 밀린 도형들이 내려옴. 그리고 다시 테트리스 검사, 있으면 2번부터 반복

tetris_blue()/tetris_green()은 각각 파란/초록색 영역의 테트리스를 확인해서 존재시 해당 열을 제거하고 true 반환, 테트리스 없으면 false하는데, 테트리스가 있을 경우 while문에 들어가 테트리스 이후에 도형 내리는 작업인 push_block_blue()/push_block_green()을 하였다. 마지막으로 검사된 조건에서 테트리스가 발생하지 않았으면 해당 반복을 종료한다.

 

4. 연한부분내 도형확인, 연한부분내 도형이 있는 칸만큼 아래 블록들 내림

int vagueBlue = check_vague_blue();
if(vagueBlue > 0) {
  for (int i = 5-vagueBlue; i >= 2-vagueBlue; i--) {
    for (int j = 0; j < 4; j++) {
      BLUE[j][i+vagueBlue] = BLUE[j][i];
    }
  }
  for (int i = 2-vagueBlue; i < 2; i++) {
    for (int j = 0; j < 4; j++) { BLUE[j][i] = 0; }
  }
}
int vagueGreen = check_vague_green();
if(vagueGreen > 0) { // vagueBlue
  for (int i = 5-vagueGreen; i >= 2-vagueGreen; i--) {
    for (int j = 0; j < 4; j++) {
      GREEN[i+vagueGreen][j] = GREEN[i][j];
    }
  }
  for (int i = 2-vagueGreen; i < 2; i++) {
    memset(GREEN[i], 0, sizeof(int)*4);
  }
}
}

check_vague_blue()/check_vague_green() 두 함수를 통해 연한부분내 도형을 검사하고 있는 칸만큼 전체 도형을 아래/우측으로 민다.

 

5. 다시 도형을 입력받을 때마다 1부터 반복

 

 

* 문제 자체에서 요구하는 알고리즘 자체가 엄청나게 어려운 것은 아니었으나, 문제 설명과 조건들을 전부 이해하는데 시간이 많이 소요되었다. 사실 첫번째 이 문제를 풀었을 때 실패하여 다시 도전해서 풀이하였는데, 아무래도 도형을 내리고 테트리스를 반복하는 부분에서의 로직이 첫번째 풀이에서 부정확했던 것 같다.

 

C. 풀이

1. 블록의 입력, 그리고 파란/초록색 영역으로의 이동(내려가기)

2. 테트리스 확인, 한 줄이 블록으로 가득 찬 경우 해당 열/행 제거 + 점수 추가

3. 테트리스 후, 없어진 열/행에 밀린 도형들이 내려옴. 그리고 다시 테트리스 검사, 있으면 2번부터 반복

4. 연한부분내 도형확인, 연한부분내 도형이 있는 칸만큼 아래 블록들 내림

5. 다시 도형을 입력받을 때마다 1부터 반복

6. 마지막 도형이 들어올 때까지 반복, 최종 점수와 초록/파란색 영역내 남은 도형의 갯수 반환

 

D. 내 코드