프렌즈4블록

 

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

프로그래머스

 

Level 2 

 

모바일 게임의 일부를 구현해야하는 문제.

 

4개 모여서 터트릴 경우와 더불어 맵의 프렌즈들을 다시 끌어내리고 터트릴 수 없을 때까지 진행해야한다.

 

 

 

다음과 같은 기능들을 구현해야하는데 BFS 를 쓰기엔 터트리고 맵을 정리한뒤 다시 터트려야 하기때문에 

높은 시간 복잡도를 피하기엔 제한 시간 내에 구현하기 힘들 것 같아 완전 탐색으로 구현했다.

 

 

일단 좌상단에서 우하단까지 0 ~ m-1, 0 ~ n-1 까지 완전 탐색을 진행했다.

어차피 4개의 사각형 모양으로 고정이니 가장 바깥쪽은 확인할 필요가 없기 때문이다.

 

 

다음으로는 터트리는 순서를 선입 선출로 진행했다. 

상단부터 터트려가며 빈 공간은 점수로 치지 않고 터트린 곳을 빈 공간으로 만들며 점수를 가산했다. 

 

 

마지막으로 터트린 후 빈 공간을 정리하는 것을 큐를 활용해 선입 선출로 아래서부터 채워나가는 방법으로 구현했다. 

 

 

import java.util.*;

public class Solution { //프렌즈4블록
    static int maxRow;
    static int maxCol;
    public int solution(int m, int n, String[] board) {
        maxRow = m;
        maxCol = n;
        char[][] map = new char[maxRow][maxCol];
        for(int lineIdx = 0; lineIdx < board.length; lineIdx++){
            for(int idx = 0; idx < board[lineIdx].length(); idx++){
                map[lineIdx][idx] = board[lineIdx].charAt(idx);
            }
        } //문자열 Character 로 Split
        int answer = 0;
        while(!isEnd(map)){ //맵에 더 터트릴 프렌즈4가 있을 경우 종료
            Queue<int[]> popQueue = new LinkedList<int[]>(); //터트릴 수 있는 좌상단 좌표 큐
            for(int row = 0; row < maxRow-1; row++){
                for(int col = 0; col < maxCol-1; col++){ //완전 탐색 하며 터트릴 수 있는 좌표들 확인
                    if(map[row][col] == ' ')
                        continue;
                    if(map[row][col] != map[row+1][col])
                        continue;
                    if(map[row][col] != map[row][col+1])
                        continue;
                    if(map[row][col] != map[row+1][col+1])
                        continue;
                    popQueue.add(new int[]{row, col});
                }
            }
            int size = popQueue.size();
            for(int cnt = 0; cnt < size; cnt++){ //터트릴 좌표들 터트리면서 점수 추가
                int[] pop = popQueue.poll();
                if(map[pop[0]][pop[1]] != ' '){
                    map[pop[0]][pop[1]] = ' ';
                    answer++;
                }
                if(map[pop[0]+1][pop[1]] != ' '){
                    map[pop[0]+1][pop[1]] = ' ';
                    answer++;
                }
                if(map[pop[0]][pop[1]+1] != ' '){
                    map[pop[0]][pop[1]+1] = ' ';
                    answer++;
                }
                if(map[pop[0]+1][pop[1]+1] != ' '){
                    map[pop[0]+1][pop[1]+1] = ' ';
                    answer++;
                }
            } //큐에 좌표가 좌상단 -> 우하단으로 진행되서 중복으로 터지는 칸들을 예외처리 가능
            sortMap(map); // 터트린 후 맵 정리
        }

        return answer;
    }
    public boolean isEnd(char[][] map){
        for(int row = 0; row < maxRow-1; row++){
            for(int col = 0; col < maxCol-1; col++){
                if(map[row][col] != ' ' && map[row][col] == map[row+1][col] && map[row][col] == map[row][col+1] && map[row][col] == map[row+1][col+1])
                    return false;
            }
        }
        return true;
    }
    public void sortMap(char[][] map){
        for(int col = 0; col < maxCol; col++){ //좌상단에서 좌하단으로 공백이 아닌 프렌즈들 취합
            Queue<Character> lineQueue = new LinkedList<Character>();
            for(int row = maxRow-1; row > -1; row--){
                if(map[row][col] != ' ')
                    lineQueue.add(map[row][col]);
                map[row][col] = ' '; //취한한 후 임시로 공백으로 만듬
            }
            int queueSize = lineQueue.size();
            for(int idx = maxRow-1; idx >= maxRow-queueSize; idx--){ //공백인 열에서 다시 최하단부터 큐에서 프렌즈를 꺼내 넣어줌
                map[idx][col] = lineQueue.poll();
            }
        }
    }
}