프로그래머스 - [1차] 프렌즈4블록

프로그래머스 - [1차] 프렌즈4블록

class Solution {
	char[][] map;

	public int solution(int m, int n, String[] board) {
		int answer = 0;
		// 1. 게임판에 옮겨놓기
		map = new char[m][n];
		for (int i = 0; i < m; i++) {
			map[i] = board[i].toCharArray();
		}
		/*
		2. 게임을 아래의 순서로 진행한다.
		  - 2-1. 없앨 블록을 찾고(없으면 종료)
		  - 2-2. 게임 판을 밑으로 내리고 반복
		 */

		while (true) {
			// 없앨 수 있는 블록의 개수 추출
			int cnt = clearBlock(m, n);
			// 더이상 없앨 수 있는 블록이 없다면 게임 종료
			if (cnt == 0) {
				break;
			}
			answer += cnt;
			// 밑으로 당기기
			dropBlock(m, n);
		}

		return answer;
	}

	/*
		2-1. 게임을 진행한다.
		- 조건에 맞으면 없앨 수 있는 블록의 개수 반환
		  - 해당 블록 우측, 아래, 우측 대각선 아래, 본인 => 총 4개가 인접한 것을 찾음
		  - 찾으면 graph를 true 상태로 변경
		- 전체 다 돌고 나서 true것의 개수를 반환
	 */
	private int clearBlock(int m, int n) {
		int[] dx = {0, 0, 1, 1};
		int[] dy = {0, 1, 0, 1};
		// 삭제할 수 있는지 검사하는 그래프
		boolean[][] check = new boolean[m][n];
		// 게임판 전체 순회
		for (int i = 0; i < m - 1; i++) {
			for (int j = 0; j < n - 1; j++) {
				char block = map[i][j];
				// 비워진 블락이라면 다음 문자 검사
				if (block == ' ')
					continue;
				// 해당 문자 인접 부분이 삭제 가능한지 나타내는 flag변수
				boolean canClear = true;
				// 인접한 부분(본인, 우측, 우측 대각선, 아래) 모두 같은 문자인지 검사
				for (int k = 0; k < 4; k++) {
					if (map[i + dx[k]][j + dy[k]] != block) {
						canClear = false;
						break;
					}
				}
				// 삭제할 수 있다면 true로만 변경
				// true로만 변경 해둬야 인접한 또 다른 조건이 만족할 때 영향을 안받을 수 있음
				if (canClear) {
					for (int k = 0; k < 4; k++) {
						check[i + dx[k]][j + dy[k]] = true;
					}
				}
			}
		}

		int cnt = 0;
		// 삭제 처리 및 개수 반환
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (check[i][j]) {
					cnt++;
					map[i][j] = ' ';
				}
			}
		}

		return cnt;
	}

	/*
		없어진 블록이 있다면 그 자리를 위의 블록으로 매꾸기(내리기)
		- idx : 채워질 부분(공백) => 초기값 : 맨 마지막 행을 가르킴
		  - 공백이 아니라면 for문 조건 만족해서 자기 자신 넣기
		  - 이후 행을 하나씩 올라가며 공백인것을 만나면 그대로 올라가며 검사
		  - 공백이 아닌 녀석을 발견하면 공백인 idx에 넣어준다.
	 */
	private void dropBlock(int m, int n) {
		for (int i = 0; i < n; i++) {
			int idx = m - 1;
			for (int j = m - 1; j >= 0; j--) {
				if (map[j][i] != ' ') {
					char temp = map[j][i];
					map[j][i] = ' ';
					map[idx--][i] = temp;
				}
			}
		}
	}
}

전체 로직

• 게임판 생성
• 삭제할 수 있는 블록 찾기
• 삭제할 수 있는 블록이 있다면 삭제 처리하고 게임판의 블럭을 밑으로 내림
• 삭제할 수 있는 블록이 없다면 게임 종료

삭제할 수 있는 블록 찾기

• 본인, 우측, 아래, 우측 대각선 아래가 같으면 삭제 대상 블록이다.
• 하지만 이를 발견하자 마자 삭제하면, 중첩되어 삭제되는 경우들이 모두 적용되지 않는다.
  
  • 2, 3, 4 번째 그림에서 1번 조건 다 삭제한다면 2, 3, 4 블록들은 삭제가 안될것!
• 그래프를 전체 순회하며 기본 조건을 만족하는 부분을 찾고, 해당 만족 부분을 바로 삭제하지 않고 flag 표시만 해둔다.(위 그림에서 2, 3, 4 case도 모두 정상 동작하기 위해)
  • 순회하는 대상 문자가 조건을 만족하지 않으면 for문을 탈출하여 다음 문자 탐색을 통해 연산 횟수 절약
• true의 수 만큼 반환하고, 해당 인덱스를 공백문자(' ')처리를 하여 삭제 처리를 한다.

(삭제할 수 있는 블록이 있다면) 게임판의 블록 내림

• 게임판에 생긴 중간 빈공간을 위에 있는 블록을 내려 채운다.
• 이를 위해 열을 순회하며 마지막 행부터 빈공간을 위쪽의 문자와 바꿔준다.
  • idx : 채워질 부분(공백) => 초기값 : 맨 마지막 행을 가르킴
  • (탐색 문자가 공백이 아니라면) for문 조건 만족해서 자기 자신 넣기
  • (공백이 아닌 녀석을 발견하면) 공백인 idx에 넣어주고 삭제 처리

어렵군..

• 출처 : 뤼튼