[2018 상반기 카카오 블라인드 채용 1차] 프로그래머스 카카오 프렌즈4블록(난이도 상)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17679

※ 추천 선행 알고리즘 : 우선 탐색, DP

문제 설명

프렌즈4블록

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

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

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

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

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

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

Algorithm

* First Search(DFS, BFS)로 접근을 해보았지만 동일한 7번 테스트케이스에서 계속 오류가 잡혀 해결하지 못했는데 해결 방법 아시는 분??👋

2*2 형태의 군집을 찾아 제거 후 제거된 군집의 개수를 구하시오.(단, 군집을 제거 했을 때 위에 있는 원소들은 내려오는 것을 주의 할 것)

1. "위에서 아래로", "아래에서 위로" 둘중 하나의 형태로 원소를 찾는다. (단, 방식에 따라 for문의 수식을 주의해가며 짤 것)

대신 찾음과 동시에 해당 borad에서는 값을 바꾸지 않는다. 이러한 이유는 2*2형태의 군집을 찾았을 때, 다음과 같은 상황을 방지하기 위함이다.

T T T A N T

R R F A C C

R R R F C C

T R R R A A

T T M M M F

T M M T T J

왼쪽에 있는 빨간색 구간일 때의 2*2 군집, 그 오른쪽 파란색 구간일 때도 2*2 군집 이기에 빨간군집[2][2]의 R이 겹치게 된다.

따라서, 새로운 보드판을 하나 더 생성하여 군집으로 읽힌 곳을 check 하여 count에 차질이 없도록 한다.

2. 1번의 알고리즘을 통해 한바퀴 다 돌았다면 check 된 index 위치들을 모두 board에서 '*'로 바꾸어준 후, 위 원소를 아래로 내린다.

바꿀 때는 아래서 위로 가야하니 반복문 조건식에 주의해가며 작성하도록 하자.

3. 1~2번 알고리즘을 반복한다.(더 이상의 count가 되지 않는 시점까지(즉, 군집이 없을 때까지))

반복하기 전 check용도로 사용되었던 배열은 초기화해주어야 한다. 그렇지 않으면 전에 check했던 부분이 check 되어있기 때문이다.

4. 1~3번을 모두 처리한 알고리즘을 소스코드로 보면 다음과 같다.

//kuklife.tistory.com   #include <string> #include <vector> #include <iostream> using namespace std; int solution(int m, int n, vector<string> board) { int answer = 0; vector<vector<int>>temp(m); //temp : 군집 발견 check 용도 for (int i = 0; i < m; i++) temp[i].resize(n, 0); while (true) { int count = 0; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (board[i][j] != '*') { if (board[i][j] == board[i][j - 1] && board[i][j] == board[i - 1][j] && board[i][j] == board[i - 1][j - 1]) { if (temp[i][j] == 0) { temp[i][j] = 1; count++; } if (temp[i][j - 1] == 0) { temp[i][j - 1] = 1; count++; } if (temp[i - 1][j] == 0) { temp[i - 1][j] = 1; count++; } if (temp[i - 1][j - 1] == 0) { temp[i - 1][j - 1] = 1; count++; } } } } } answer += count; if (count == 0) break; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (temp[i][j] == 1) { board[i][j] = '*'; temp[i][j] = 0; } for (int i = 0; i < n; i++) for (int j = m - 1; j >= 0; j--) if (board[j][i] == '*') for (int z = j-1; z >= 0; z--) if (board[z][i] != '*') { swap(board[z][i], board[j][i]); j--; } } return answer; }