[Programmers] 프렌즈4블록

[문제 링크]

프로그래머스

 

[생각 흐름]

dfs를 이용하여 각 좌표에서 사각형기준을 깊이 선탐색으로 진행함 --> 시간 초과(TC 4, 8, 11)

메인에서 그냥 모든 경우 비교하기, stack or queue 이용해서 삭제된 칸 정리 (삭제된 칸은 ' . ' 으로 정리하고 다음 진행시에는 ' . '는 무시하고 지나가기 ) 

state는 방문 처리 노드로 만약 이전에 방문된 노드라면 cnt 증가시키지 않고, 방문이 되지 않은 경우에만 cnt++

종료 시점은 while 을 한번더 반복하였을때 이전값과 같은경우 return 하도록 함 

 

[코드]

import java.util.Stack;

class Solution {
    private static boolean[][] state;
    private static void move(char arr[][]) {
        Stack<Character> s = new Stack<>();

        for (int j = 0; j < arr[0].length; j++) {
            for (int i = 0; i< arr.length; i++) {
                if (!state[i][j]) {
                    s.push(arr[i][j]);
                }
                arr[i][j] ='.';
            }

            int size = s.size();
            for(int i=0;i<size;i++){
                arr[arr.length-i-1][j]=s.pop();
            }
        }
    }

    public int solution(int m, int n, String[] board) {
        int cnt =0;
        int answer = 0;
        char[][] arr = new char[m][n];
        for (int i = 0; i < m; i++) arr[i] = board[i].toCharArray();

        while (true) {
            answer = cnt;
            state = new boolean[m][n];
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    if (arr[i][j]=='.') continue;
                    if (arr[i][j] == arr[i][j + 1] && arr[i][j] == arr[i + 1][j] && arr[i][j] == arr[i + 1][j + 1]) {
                        int[] tempx = {0,0,1,1};
                        int[] tempy ={1,0,1,0};
                        for(int k=0;k<4;k++){
                            if(!state[i+tempx[k]][j+tempy[k]]){
                                cnt++;
                                state[i+tempx[k]][j+tempy[k]] = true;
                            }
                        }
                    }
                }
            }
            
            
            if (answer == cnt) break;
            move(arr);

        }

        return cnt;
    }

}