[프로그래머스] 2018 KAKAO BLIND RECRUITMENT - 프렌즈4블록

문제 설명

프렌즈4블록

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

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

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

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

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

xxxxxxxxxx
TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(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개의 블록이 지워진다.

 

 

풀이

백준에 뿌요뿌요 문제와 유사한 문제입니다

 

맨처음에 2x2 맵을 어떻게 구분해줄까 라는 것에 대해서 고민을 해봤습니다

 

0,0 0,1

1,0 1,1

 

이렇게 4개의 맵이 있다면

0,0을 기준으로 왼쪽, 아래, 대각선 좌표만 확인을 하면 2x2맵을 확인 할 수 있습니다

 

문제를 풀면서 많은 시간을 허비했던 것에 대해서 말씀 드리자면

visited 배열을 사용하지 않고(어차피 방향은 왼쪽,아래,대각선만 가니 중복된 자기 자신이 들어 올리가 없다) 라고 생각해서 문제를 풀었는데

 

중복된 위치가 들어 올 수 있었습니다.

 

예를들어서

 

CCBDE

AAADE

AAABF

 

이 경우 2x2맵이 2개로 겹쳐진 모습을 볼 수 있는데 이때 중복된 좌표가 들어 올 수 있었습니다.

 

그리고 이 문제의 종료조건은 더이상 블록을 지울수 없을때까지 진행되니

while(true)문으로 계속 블록을 지우고, 맵을 떨어트리는 과정을 반복하는데

더 이상 블록을 지울수 없을때를 boolean 문으로 분기처리해서 끝내주면 됩니다.

 

전체코드

import java.util.*;
class Solution {
    static int global_m;
    static int global_n;
    static String map[][];
    static int dx[] = {0,1,1};
    static int dy[] = {1,0,1};
    static int ans =0;
    static boolean game_end;
        public static int solution(int m, int n, String[] board) {
 
        global_m = m;
        global_n= n;
        map = new String[m][n];
        
        // map input
        for(int i=0; i<m; i++) {
            String [] t = board[i].split("");
            for(int j=0; j<n; j++) {
                map[i][j] = t[j];
            }
        }
        
        while(true) {
            game_end = true;
            for(int i=0; i<m; i++) {
                for(int j=0; j<n; j++) {
                    if(!map[i][j].equals(".")) {
                        if(isPossible(i,j)){
                            bfs(i,j);
                            game_end = false;
                        }
                    }
                }
            }
            map_down();
            
            if(game_end) {
                break;
            }
        }   
        return ans;
    }
    public static void map_down() {
        for(int i=global_m-1; i>=0; i--) {
            for(int j=0; j<global_n; j++) {
                if(map[i][j].equals(".")) {
                    int remove = i-1;
                    while(remove>=0) {
                        if(!map[remove][j].equals(".")) {   
                            map[i][j] = map[remove][j];
                            map[remove][j] = ".";
                            break;
                        }
                        remove--;
                    }
                }
            }
        }   
    }
    public static void bfs(int x, int y) {
        boolean visited[][] = new boolean[global_m][global_n];
        Queue<Node>q = new LinkedList<>();
        q.add(new Node(x,y));
        ArrayList<Node>list = new ArrayList<>();    // 블록을 빈칸으로 바꿀 위치
        list.add(new Node(x,y));
        visited[x][y]= true;
        
        
        while(!q.isEmpty()) {
            Node a= q.poll();
            if(!isPossible(a.x,a.y)) {
                continue;
            }
            for(int i=0; i<3; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(!visited[nx][ny]) {
                    q.add(new Node(nx,ny));
                    list.add(new Node(nx,ny));
                    visited[nx][ny] = true;
                }
            }
        }
        
        for(Node b: list) {
            map[b.x][b.y]= ".";
            ans++;
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<global_m && y<global_n) {
            return true;
        }
        return false;
    }
    public static boolean isPossible(int x, int y) {
        String kakaoCharacter = map[x][y];
        int cnt = 0;
        for(int i=0; i<3; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isRange(nx,ny) && map[nx][ny].equals(kakaoCharacter)) {
                cnt++;
            }
        }
        if(cnt==3) {
            return true;
        }
        return false;
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}