Candy Crush

본사 대기를 하면서 조그만한 노트북으로 풀려니 목에 담이 왔던 문제다. 사실 이 문제는 프로그래머스에서 4 곱하기 4 Grid 안에서 같은 그림이면은 터지게 되고 위에서 아래로 떨어지는 구조의 문제와 정말 같았다.

다만, 차이점은 이번에는 4 곱하기 4의 특정 window 가 아니라 가로에 쭉 이어갈 수도 있고 세로로 쭉 이어갈 수 있는 문제라는 것이다.

내가 왜 이 문제를 힘들어 했는지는 모르겠지만 같은 숫자로 이어지는 가로 / 세로 줄을 찾으면서 3중 루프로 찾으려고 했던게 문제 였던거 같다. 3중 루프 필요 없이 그냥 3개 줄만 찾으면 끝나는 문제다.

다음부터는 이런 구현 문제 나왔을때 하나씩 천천히 깨보자.

class Solution {
public:
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
        bool flag = true; 
        while(flag){
          vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(), false)); 
          flag = false; 
          for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size() - 2; j ++){
              if(board[i][j] != 0 && (board[i][j] == board[i][j+1]) && (board[i][j] == board[i][j+2])){
                visited[i][j] = true; 
                visited[i][j+1] = true; 
                visited[i][j+2] = true;
                flag = true; 
              }
            }
          }

          for(int i = 0; i < board.size() - 2; i++){
            for(int j = 0; j < board[0].size(); j++){
              if(board[i][j] != 0 && (board[i][j] == board[i+1][j]) && (board[i][j] == board[i+2][j])){
                visited[i][j] = true; 
                visited[i+1][j] = true; 
                visited[i+2][j] = true; 
                flag = true; 
              }
            }
          }

          if(flag){
            for(int i = 0; i < visited.size(); i++){
              for(int j = 0; j < visited[0].size(); j++){
                if(visited[i][j] == true){
                  board[i][j] = 0; 
                  for(int k = i; k > 0; k--){
                    int swap = board[k-1][j]; 
                    board[k-1][j] = 0; 
                    board[k][j] = swap; 
                  }
                }
              }
            }
          }
        }

      return board; 
    }
};