[프로그래머스] 프렌즈4블록 (JAVA)

개츠비·2023년 5월 15일

프로그래머스

목록 보기

11/16

소요시간 : 35분
문제 사이트 : 프로그래머스
문제 수준 : 레벨 2
문제 유형 : 구현, 시뮬레이션
다른 사람의 풀이를 참고 했는가 ? : X
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17679
푼 날짜 : 2023.05.15

✨ 카카오 1차 코딩테스트 문제.

1. 사용한 자료구조 & 알고리즘

스택, 큐, 구현, 시뮬레이션

2. 사고과정

문제를 잘못 이해해서 2 x 2 블록이 있다면 거기서 이어지는 블록은 모두 제거하는줄 알고 dfs로 문제를 풀려다가 계속 틀려서 좀 헤맸다.

2 x 2 블록에서 중복은 어떻게 탐색할 것인가?
-> 2 x 2 블록의 종류가 모두 같은 것을 탐색했다면, 바로 제거하지 말고 우선 queue에 그 위치를 담아둔다. 그리고 2중 for문으로 모든 map에서의 탐색을 마쳤다면, 그때 queue에 담아 놓은 위치의 블록을 제거하면 된다.
👉 그리고 4개의 블록을 다 담을 필요 없이, 가장 왼쪽 위 블록 1개만 담아 놓고, queue에서 처리할 때 그 블록을 기준으로 4개 제거해주면 된다. 제거한 것은 '0'으로 처리했다.
✔️ 만약 2 x 2 블록의 종류가 모두 같다고 곧바로 제거하면, 제거한 블록이 다른 블록의 2 x 2 의 범위에 탐색되는 것을 막기 때문에, 2차원 map을 탐색한 후, 한 번에 처리해줘야 한다.

제거하여 떨어지는 블록은 어떻게 처리할 것인가?
맨 위에서부터 세로선마다 '0' 이 아닌 블록들을 stack에 담는다. 그 후 블록은 '0'으로 처리해준다. 그리고 한 줄 모두 Stack에 담았다면, 그 후 그 세로선마다 맨 아래에서부터 스택이 비지않았다면 pop해준다. 그러면 우선 모든 블록은 0 으로 처리되었다가, 다시 0이 아닌 블록들을 pop하면서 이동한 것으로 처리할 수 있다.

3. 풀이과정

2 x 2 블록이 있나 탐색. 있는 동안 while문이 반복된다. 2 x 2 블록이 있다면 그 블록은 '0'으로 처리해준다. 하나라도 바뀌었다면 while문이 반복된다.
그리고 Stack을 통해서 같은 세로선 라인의 '0'이 아닌 블록을 탐색하고, 다시 pop하면서 블록들이 이동한 것으로 처리한다.
반복문이 종료되었다면, 더 이상 제거할 블록이 없는 것이다. map에서 '0'이 있다면 그 count를 세어준 것이 제거한 블록의 개수이다. 그 count를 return

4. 소스코드

import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
class Solution {
    static char map[][];
    static boolean visited[][];
    
    public int solution(int m, int n, String[] board) {
        map=new char[m][n];
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                map[i][j]=board[i].charAt(j);
            }
        }
        while(check()) {
            removeBlock();
        }
        
        int count = 0;
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                if(map[i][j]=='0'){
                    count++;
                }
            }
        }
       
        
        
        return count;
    }
    
    public static boolean check() {
        visited=new boolean[map.length][map[0].length];
        boolean find=false;
        Queue<Integer[]> queue=new LinkedList<>();
        for(int i=0;i<map.length-1;i++){
            for(int j=0;j<map[0].length-1;j++){
                int now=map[i][j];
                if(now=='0') continue;
                if(map[i][j+1]==now&&map[i+1][j]==now&&map[i+1][j+1]==now){
                  queue.add(new Integer[]{i,j});
                    find=true;
                }
            }
        }
        
        while(!queue.isEmpty()) {
            Integer now[]=queue.poll();
            int y=now[0];
            int x=now[1];
            map[y][x]='0';
            map[y][x+1]='0';
            map[y+1][x]='0';
            map[y+1][x+1]='0';
        }
        
        
        return find;
        
    }
    public static void removeBlock(){
        
        for(int i=0;i<map[0].length;i++){
            Stack<Character> stack=new Stack<>();
            for(int j=0;j<map.length;j++){
               if(map[j][i]!='0'){
                   stack.push(map[j][i]);
               }
                
                map[j][i]='0';
            }
         
            for(int j=map.length-1;j>=0;j--){
               if(!stack.isEmpty()) {
                   map[j][i]=stack.pop();
               }
                
            }
            
        }
        
        
    }

    
    
}