2018 - [1차] 프렌즈4블록

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

코딩테스트 연습 - [1차] 프렌즈4블록

[ 문제풀이 ]

삼성 기출문제에서 많이 풀어본 전형적인 시뮬레이션 문제이다. 삼성 문제에 비해 별다른 조건이 없기 때문에 굉장히 쉽게 해결할 수 있다.

​구현하기 쉽게 주어진 문자열 board를 2차원 map으로 변환하자.

​모든 맵을 돌면서 제거할 수 있는 블록들을 체크하여 제거한 후 블록들을 이동시키면 된다. 주의해야 할 점은 이동한 후 또 제거될 수도 있기 때문에 한 번만 확인해서는 안 된다.

import java.util.*;

class Solution {
	char[][] map;
	boolean[][] visit;
	Stack<Character> stack;

	public int solution(int m, int n, String[] board) {
		map = new char[m][n];
		visit = new boolean[m][n];
		stack = new Stack<>();

		//구현하기 쉽게 2차원 map으로 변환
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				map[i][j] = board[i].charAt(j);
			}
		}

		boolean finish;
		do {
			finish = false;

			//제거되는 블록이 존재한다면
			if (isValid(m, n)) {
				finish = true;
				
				//블록들을 제거
				removeBlock(m, n);
				
				//블록들을 아래로 이동
				moveBlock(m, n);
				
				for (int i = 0; i < m; ++i) {
					Arrays.fill(visit[i], false);
				}
			}
		} while (finish);

		return getAnswer(m, n);
	}

	public boolean isValid(int m, int n) {
		boolean check = false;

		for (int i = 0; i < m - 1; ++i) {
			for (int j = 0; j < n - 1; ++j) {
				if (map[i][j] == '\0') continue;
				
				if (map[i][j] == map[i + 1][j] && map[i][j] == map[i][j + 1] 
                         && map[i][j] == map[i + 1][j + 1]) {
					check = true;
					visit[i][j] = true; visit[i + 1][j] = true;
					visit[i][j + 1] = true; visit[i + 1][j + 1] = true;
				}
			}
		}

		return check;
	}

	public void removeBlock(int m, int n) {
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (visit[i][j]) {
					map[i][j] = '\0';
				}
			}
		}
	}

	public void moveBlock(int m, int n) {
		for (int j = 0; j < n; ++j) {
			for (int i = 0; i < m; ++i) {
				if (map[i][j] != '\0') {
					stack.push(map[i][j]);
					map[i][j] = '\0';
				}
			}
			
			int row = m - 1;
			while (!stack.isEmpty()) {
				map[row--][j] = stack.pop();
			}
		}
	}

	public int getAnswer(int m, int n) {
		int answer = 0;

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

		return answer;
	}
}