Dev 일기장

1. 문제

programmers.co.kr/learn/courses/30/lessons/17679

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은프렌즈4블록.
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

제한 사항

입력 형식

• 입력으로 판의 높이m, 폭n과 판의 배치 정보board가 들어온다.
• 2 ≦n,m≦ 30
• board는 길이n인 문자열m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예

2. 어떻게 풀까?

1. 입력으로 주어진 String 배열 board를 이차원 배열로 만든다.
2. 이차원 배열의 현재 index의 block을 기준으로 block을 지울 수 있는지 확인한다.
3. 지운 이후 위쪽의 block들을 아래로 내린다.
4. 지울 수 있는 block이 없을 때까지 반복한다.
5. 해결 과정은 명확하게 이해할 수 있는데, 이것을 코드로 작성하는데 계속 막히고, 틀렸다. 특히, 지울 수 있는지 확인하는 과정에서 boolean 타입을 선언해서 확인하려했는데, 잘 안됐다. 그래서 답을 참고했다.

velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%94%84%EB%A0%8C%EC%A6%884%EB%B8%94%EB%A1%9D-Java

3. 코드

테스트 코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    String[] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};
    assertThat(new Solution().solution(4, 5, board), is(14));
  }

  @Test
  public void test2() {
    String[] board = {"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};
    assertThat(new Solution().solution(6, 6, board), is(15));
  }

}

실제 코드

public class Solution {

  public int solution(int m, int n, String[] board) {
    String[][] table = buildTable(m, n, board);
    int count = 0;

    while (true) {
      int dropBlockCount = countFourBlock(m, n, table);
      if (dropBlockCount == 0) {
        break;
      }
      count += dropBlockCount;
      dropTable(m, n, table);
    }

    return count;
  }

  private String[][] buildTable(int m, int n, String[] board) {
    String[][] table = new String[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        table[i][j] = board[i].charAt(j) + "";
      }
    }
    return table;
  }

  private int countFourBlock(int m, int n, String[][] table) {

    boolean[][] check = new boolean[m][n];

    for (int row = 0; row < m - 1; row++) {
      for (int col = 0; col < n - 1; col++) {
        if (table[row][col].equals(".")) {
          continue;
        }
        checkFourBlock(table, check, row, col);
      }
    }

    int count = 0;
    for (int row = 0; row < m; row++) {
      for (int col = 0; col < n; col++) {
        if (check[row][col]) {
          count++;
          table[row][col] = ".";
        }
      }
    }

    return count;
  }

  private void checkFourBlock(String[][] table, boolean[][] check, int currentRow,
      int currentCol) {
    String currentBlock = table[currentRow][currentCol];

    for (int row = currentRow; row < currentRow + 2; row++) {
      for (int col = currentCol; col < currentCol + 2; col++) {
        if (!table[row][col].equals(currentBlock)) {
          return;
        }
      }
    }

    for (int row = currentRow; row < currentRow + 2; row++) {
      for (int col = currentCol; col < currentCol + 2; col++) {
        check[row][col] = true;
      }
    }
  }

  private void dropTable(int m, int n, String[][] table) {
    for (int col = 0; col < n; col++) {
      for (int row = m - 1; row >= 0; row--) {
        if (table[row][col].equals(".")) {
          for (int notDotRow = row - 1; notDotRow >= 0; notDotRow--) {
            if (!table[notDotRow][col].equals(".")) {
              table[row][col] = table[notDotRow][col];
              table[notDotRow][col] = ".";
              break;
            }
          }
        }
      }
    }
  }

}

• buildTable()에서 일차원 배열의 board를 이차원 배열로 만들었다.
• 반복문을 돌며 countFourBlock()을 통해 지울 수 있는 block의 수를 계산 후, 전체 count에 더해주고 dropTable()을 통해 지웠다.
• countFourBlock()에서 지울 수 있는 block인지 확인하는 boolean 이차원 배열을 선언 후, checkFourBlock()을 통해그림의 왼쪽 위부터 차례대로 확인했다. 마지막 행과 열은 확인 할 수 없기 때문에 반복문을 m-1, n-1까지만 돌며 확인했다. 지울 수 있는 block은 .으로 바꿔주었다.
• dropTable()에서 element가 .인 칸을 찾은 후에 그 위로 .가 아닌 칸을 찾아서 두 element를 바꿔주었다.

4. 느낀 점

이차원 배열을 왼쪽 위부터 오른쪽 아래까지 차례대로 확인 👉 지울 수 있는 블록이라면 따로 마킹 👉 이차원 배열에서 마킹해놓은 개수를 덧셈 👉 블록들 삭제 👉 지울 수 있는 블록이 없을 때까지 반복

이라는 흐름은 머리로 간단히 그려졌는데, 막상 코드로 구현하려고 할 때 어려움을 느꼈다.

마킹을 어떻게 해야할까? Key, Value로 구현해야하나? 그럼 Entry를 써야하나? 이런 고민들도 있었고,

지울 수 있는 블록들은 어떻게 삭제를 해야할까? 배열에서는 delete하기 어려우니 List를 써야하나? 하는 고민도 있었다.

다른 분이 푼 코드를 보니, 그냥 따로 boolean 타입의 이차원 배열을 선언하여 해결했고

배열은 delete 대신 .으로 바꿔주었다.

어렵다 ㅜㅜ