[1차] 프렌즈4블록

문제 풀러가기

문제 설명

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

01

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

02

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

03

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

04

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

T T T A N T
R R F A C C
R R R F C C
T R R R A A
T T M M M F
T M M T T J

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

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

입력 형식

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

출력 형식

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

입출력 예제

m n board answer
4 5 [“CCBDE”, “AAADE”, “AAABF”, “CCBBF”] 14
6 6 [“TTTANT”, “RRFACC”, “RRRFCC”, “TRRRAA”, “TTMMMF”, “TMMTTJ”] 15

예제에 대한 설명

  • 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
  • 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

코드

import java.util.*;

class Solution {
  public int solution(int m, int n, String[] board) {
    int answer = 0;
    char[][] map = new char[m][n];

    for(int i = 0; i < m; i++) {
      map[i] = board[i].toCharArray();
    }

    while(true) {
      int cnt = checkBlock(m, n, map);

      if(cnt == 0) break;
      answer += cnt;

      dropBlock(m, n, map);
    }

    return answer;
  }

  private void dropBlock(int m, int n, char[][] map) {
    for(int c = 0; c < n; c++) {
      for(int r = m - 1; r >= 0; r--) {
        if(map[r][c] == '.') {
          for(int nr = r - 1; nr >= 0; nr--) {
            if(map[nr][c] != '.') {
              map[r][c] = map[nr][c];
              map[nr][c] = '.';
              break;
            }
          }
        }
      }
    }
  }

  private int checkBlock(int m, int n, char[][] map) {
    int cnt = 0;
    boolean[][] isChecked = new boolean[m][n];

    for(int i = 0; i < m - 1; i++) {
      for(int j = 0; j < n - 1; j++) {
        if(map[i][j] == '.') continue;
        checkFour(map, isChecked, i, j);
      }
    }

    for(int i = 0; i < m; i++) {
      for(int j = 0; j < n; j++) {
        if(isChecked[i][j]) {
          cnt++;
          map[i][j] = '.';
        }
      }
    }

    return cnt;
  }

  private void checkFour(char[][] map, boolean[][] isChecked, int i, int j) {
    char block = map[i][j];

    for(int r = i; r < i + 2; r++) {
      for(int c = j; c < j + 2; c++) {
        if(map[r][c] != block) return;
      }
    }

    for(int r = i; r < i + 2; r++) {
      for (int c = j; c < j + 2; c++) {
        isChecked[r][c] = true;
      }
    }
  }
}

설명

같은 모양의 블록이 2x2 형태로 4개가 붙으면 사라지는데, 겹쳐있는 경우에도 지워진다. 주어진 높이와 폭을 가진 판의 형태를 가진 배열을 만들고 배열 요소로 입력된 문자열을 나눠서 입력한다. 사라질 블록을 체크하고 체크된 블록을 지우고 블록을 떨어뜨리는 것을 반복한다.

import java.util.*;

class Solution {
  public int solution(int m, int n, String[] board) {
    int answer = 0;
    char[][] map = new char[m][n];

    for(int i = 0; i < m; i++) {
      map[i] = board[i].toCharArray();
    }

    while(true) {
      int cnt = checkBlock(m, n, map);

      if(cnt == 0) break;
      answer += cnt;

      dropBlock(m, n, map);
    }

    return answer;
  }

빈 공간에 블록을 떨어뜨리는 코드이다.

  private void dropBlock(int m, int n, char[][] map) {
    for(int c = 0; c < n; c++) {
      for(int r = m - 1; r >= 0; r--) {
        if(map[r][c] == '.') {
          for(int nr = r - 1; nr >= 0; nr--) {
            if(map[nr][c] != '.') {
              map[r][c] = map[nr][c];
              map[nr][c] = '.';
              break;
            }
          }
        }
      }
    }
  }

체크된 블록을 모두 지우는 코드이다.

  private int checkBlock(int m, int n, char[][] map) {
    int cnt = 0;
    boolean[][] isChecked = new boolean[m][n];

    for(int i = 0; i < m - 1; i++) {
      for(int j = 0; j < n - 1; j++) {
        if(map[i][j] == '.') continue;
        checkFour(map, isChecked, i, j);
      }
    }

    for(int i = 0; i < m; i++) {
      for(int j = 0; j < n; j++) {
        if(isChecked[i][j]) {
          cnt++;
          map[i][j] = '.';
        }
      }
    }

    return cnt;
  }

사라질 블록을 체크하는 코드이다.

  private void checkFour(char[][] map, boolean[][] isChecked, int i, int j) {
    char block = map[i][j];

    for(int r = i; r < i + 2; r++) {
      for(int c = j; c < j + 2; c++) {
        if(map[r][c] != block) return;
      }
    }

    for(int r = i; r < i + 2; r++) {
      for (int c = j; c < j + 2; c++) {
        isChecked[r][c] = true;
      }
    }
  }
}