[프로그래머스] 2018 카카오 블라인드 #6 프렌즈4블록 (Java)

#6 프렌즈4블록

난이도 : LEVEL2

유형 : 그래프 / 시뮬레이션

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

▸ 문제

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

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

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

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

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

2018 기출 중에서 가장 풀이가 긴 문제이다. 그래프 시뮬레이션이 원래 코드가 길긴하다. 해당 문제는 조건을 잘 살펴줘야 한다. 어려운 부분이 있었다면 맵을 업데이트 해주는 부분이었다. 한 싸이클에서 4개씩 각각 터트려줘야 할지 한 번에 모아서 터트려야 할지 고민하다가 Lazy하게 모든 정보를 받은 다음 한 번에 모아서 터트리는 방법을 선택해주었다. 

 

그리고 맵을 업데이트하는 부분은 열(row) 위주로 탐색하여 -1을 빈공간으로 처리하여 Queue 자료구조를 사용하여 다음과 같이 갱신해주었다.

 

MapUpdate() 동작 방식

설계

1. 주어진 Board[]배열을 표현하고 쉽고 가볍게 다루기 위해 int[][] 2차원 배열로 변형해준다.
2. 더이상 터트릴 블록이 없을 때 까지 반복문을 돌려준다. if(removeList.size()==0) break;
   1. 2x2 블록을 브루트포스로 모두 탐색하여준다.
   2. 탐색한 모든 블록들의 위치를 저장시켜준다. removeList.add(new int[] {j,i});
3. 탐색이 다 되었을 경우 한 번에 처리하기 위해 삭제할 블록들을 터트려준다. mapIndexing();
   1. 각 위치에 '-1'이라는 표시를 해준다.
4. Queue를 사용하여 -1은 빈공간으로 처리하여 맵을 갱신해준다. mapUpdate();

 

풀이 코드 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    static int gn, gm;
	static int[][] map;
	static int[] dx = {0, 1, 1, 0};
	static int[] dy = {0, 0, 1, 1};
    
    public int solution(int m, int n, String[] board) {
       int answer = 0;
        
        gn = n;
        gm = m;
        // A~Z : 0~25
        map = new int[gm][gn];
        for(int i=0; i<gm; i++) {
        	for(int j=0; j<gn; j++) {
        		map[i][j] = board[i].charAt(j)-'A';
        	}
        }
        
        while(true) {
        	List<int[]> removeList = new ArrayList<>();
	        for(int i=0; i<gm; i++) {
	        	for(int j=0; j<gn-1; j++) {
	        		int blockSize = checkBlock(j, i, map[i][j]);
	        		if(blockSize==4) {
	        			removeList.add(new int[] {j,i});
	        		}
	        	}
	        }
	        
	        if(removeList.size()==0) break;
	        for(int[] node : removeList) {
	        	int rx = node[0];
	        	int ry = node[1];
	        	answer += mapIndexing(rx, ry);
	        	
	        }
	        mapUpdate();
        }
        return answer;
    }
	
	static int mapIndexing(int x, int y) {
		int cnt = 0;
		for(int i=0; i<4; i++) {
			int nx = x +dx[i];
			int ny = y +dy[i];
			
			if(map[ny][nx] != -1) {
				map[ny][nx] = -1;
				cnt++;
			}
		}
		return cnt;
		
	}
	
	static void mapUpdate() {
		Queue<Integer> q = new LinkedList<>();
		for(int i=0; i<gn; i++) {
        	for(int j=gm-1; j>=0; j--) {
        		if(map[j][i] !=-1) q.add(map[j][i]);
        		map[j][i] = -1;
        	}
        	
        	int h = gm-1;
        	while(!q.isEmpty()) {
        		map[h][i] = q.poll();
        		h--;
        	}
		}
		
	}
	
	static int checkBlock(int x, int y, int type) {
		int cnt =0;
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx <0 || nx > gn-1 || ny<0 || ny>gm-1) continue;
			if(map[ny][] == -1) continue;
			if(map[ny][nx] == type) {
				cnt++;
			}
		}
		return cnt;
		
	}
}