프로그래머스 프렌즈4블록 (C++)
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17679
코딩테스트 연습 - [1차] 프렌즈4블록
프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙
programmers.co.kr
문제 요약
1. 2*2블록이 모두 같은 그림으로 이루어져 있으면, 해당 블록은 사라지고 사라진 블록의 갯수만큼 점수를 얻습니다.
2. 블록은 서로 겹쳐서 터질 수 있습니다.
3. 블록은 모두 한꺼번에 사라집니다.
4. 터진 블록으로 인해 빈 공간이 생길 경우, 해당 블록의 가장 가까운 윗줄의 다른 블록이 빈 공간으로 내려옵니다.
핵심 포인트
블록을 터트리고 생기는 빈 공간을 메꿀때의 알고리즘이 중요합니다.
반드시 터진 블록의 자리에만 다른 블록이 채워지는 것은 아닙니다.
터진 블록을 채우느라 다른 블록이 자리를 매꾸고, 그렇게 새로이 빈 공간이 탄생된 다른 블록 자리에도 또 다른 블록을 채워야 할 수 있습니다.
문제 풀이
1. 편의상 n과 m의 값을 전역변수로 저장합니다. 동시에 정답값과 터트린 블록의 점수인 temp 변수를 선언합니다.
while문은 temp의 값이 0이 될때까지, 즉, 더 이상 터트릴 블록이 없을때까지 계속됩니다.
int h,w,ny,nx,my[]={0,1,1},mx[]={1,0,1}; // 전역 변수
...
int solution(int m, int n, vector<string> board) {
h = m, w = n;
int answer = 0, temp = 0;
while(true){
temp = friends(board);
answer += temp;
if(temp==0) break;
}
return answer;
}
2. 다음은 friends함수의 내부입니다. 단계별로 이해해봅시다.
int friends(vector<string> &board){
int score = 0; // 1
vector<vector<bool>> ch(h,vector<bool>(w,false));
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
if(board[i][j]!=' '){
int temp = 1;
for(int a=0; a<3; a++){
ny = i+my[a];
nx = j+mx[a];
if(ny<0||ny>=h||nx<0||nx>=w) break;
if(board[ny][nx]==board[i][j]){
temp++;
}
}
if(temp==4){
if(ch[i][j]) temp--;
else ch[i][j] = true;
for(int a=0; a<3; a++){
ny = i+my[a];
nx = j+mx[a];
if(ny<0||ny>=h||nx<0||nx>=w) break;
if(ch[ny][nx]) temp--;
else ch[ny][nx] = true;
}
score+=temp;
}
}
}
} // 터트린 블록들은 공란으로 표시함
for(int i=0; i<h; i++){ // 2
for(int j=0; j<w; j++){
if(ch[i][j]) board[i][j] = ' ';
}
}
// 터트릴 블록들은 true로 표시함
for(int i=h-1; i>=0; i--){ // 3
for(int j=0; j<w; j++){
if(board[i][j]==' '){
for(int a=i-1; a>=0; a--){
if(a<0) break;
if(board[a][j]!=' '){
board[i][j] = board[a][j];
board[a][j] = ' ';
break;
}
}
}
}
}
return score;
}
3. friends 함수의 첫 번째 구역입니다.
int score = 0; // 1
vector<vector<bool>> ch(h,vector<bool>(w,false)); // 2
for(int i=0; i<h; i++){ // 3
for(int j=0; j<w; j++){
if(board[i][j]!=' '){ // 4
int temp = 1; // 5
for(int a=0; a<3; a++){ // 6
ny = i+my[a];
nx = j+mx[a];
if(ny<0||ny>=h||nx<0||nx>=w) break; // 7
if(board[ny][nx]==board[i][j]){ // 8
temp++;
}
}
if(temp==4){ // 9
if(ch[i][j]) temp--; // 10
else ch[i][j] = true; // 11
for(int a=0; a<3; a++){ // 12
ny = i+my[a];
nx = j+mx[a];
if(ny<0||ny>=h||nx<0||nx>=w) break; // 13
if(ch[ny][nx]) temp--; // 14
else ch[ny][nx] = true; // 15
}
score+=temp; /// 16
}
}
}
} (1) score함수는 한 번에 터지는 블록의 갯수를 세어줍니다.
(2) bool문을 만들고 모든 값은 false로 초기화합니다.
(3) 블록판의 사이즈만큼 for문을 진행합니다.
(4) 만약 현재 칸이 공란이 아닐 경우...
->(5) 임시 score값인 temp를 1로 선언합니다.
->(6) 0부터 2까지 for문을 돌려줍니다. 이렇게 3가지 값만 for문으로 구하는 이유는, 2*2의 블록만 터트릴 수 있기 때문입니다. 참고로 my, mx배열은 전역변수로 이미 선언되어있습니다.
-> (7) 만약 새로운 값의 위치가 범위를 초과한다면, 바로 빠져나옵니다.
-> (8) 만약 새로운 값이 현재 값과 동일하다면 temp를 +1 합니다.
(9) 그렇게 구한 temp가 4일 경우 ...
-> (10) 만약 현재 위치가 이미 방문했던 곳이라면, temp를 -1해줍니다. 이미 터트린 블록을 중복해서 터트릴 수 없기 때문입니다.
참고로 이러한 경우는 다음의 그림과 같습니다.
-> (11) 방문한 적이 없다면 방문 표시를 해줍니다.
-> (12) 현재 위치를 기준으로 2*2의 블록만큼 for문을 돌려줍니다.
-> (13) 만약 새로운 값의 위치가 범위를 초과한다면 바로 빠져나옵니다.
-> (14) 만약 새로운 값의 위치가 이미 방문한 곳이라면, temp를 -1해줍니다.
-> (15) 그렇지 않을 경우 방문표시릉 해줍니다.
(16) 그렇게 구한 temp를 score에 더해줍니다.
4. 터트린 블록들을 모두 공란으로 표시합니다.
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
if(ch[i][j]) board[i][j] = ' ';
}
}
5. 다음은 빈 공간으로 새로운 블록이 내려오는 알고리즘입니다.
for(int i=h-1; i>=0; i--){ // 1
for(int j=0; j<w; j++){
if(board[i][j]==' '){ // 2
for(int a=i-1; a>=0; a--){ // 3
if(a<0) break; // 4
if(board[a][j]!=' '){ // 5
board[i][j] = board[a][j]; // 6
board[a][j] = ' '; // 7
break; // 8
}
}
}
}
}
return score; // 9(1) 맨 아래줄부터 for문을 진행합니다. 세로는 맨 아래줄이여야 하지만, 가로는 상관없으니 0부터 시작합니다.
(2) 만약 현재 블록이 공란이라면...
-> (3) 현재 위치의 바로 윗줄부터 0번째 줄까지 for문을 진행합니다.
-> (4) 만약 새로운 세로 위치가 음수라면, 해당 for문을 빠져나옵니다.
-> (5) 만약 새로운 위치가 공란이 아닐 경우엔...
-> (6) 현재 위치에 새로운 위치의 블록을 넣어줍니다.
-> (7) 새로운 위치는 공란으로 표시합니다.
-> (8) 해당 for문을 종료합니다.
(9) 이렇게 구한 score를 반환합니다.
6. 이렇게 블록을 터트린 다음, 더 이상 터트릴 블록이 없을 경우 while문을 빠져나와 정답을 반환합니다.
#include <string>
#include <vector>
using namespace std;
int h,w,ny,nx,my[]={0,1,1},mx[]={1,0,1};
int friends(vector<string> &board){
int score = 0;
vector<vector<bool>> ch(h,vector<bool>(w,false));
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
if(board[i][j]!=' '){
int temp = 1;
for(int a=0; a<3; a++){
ny = i+my[a];
nx = j+mx[a];
if(ny<0||ny>=h||nx<0||nx>=w) break;
if(board[ny][nx]==board[i][j]){
temp++;
}
}
if(temp==4){
if(ch[i][j]) temp--;
else ch[i][j] = true;
for(int a=0; a<3; a++){
ny = i+my[a];
nx = j+mx[a];
if(ny<0||ny>=h||nx<0||nx>=w) break;
if(ch[ny][nx]) temp--;
else ch[ny][nx] = true;
}
score+=temp;
}
}
}
} // 터트린 블록들은 공란으로 표시함
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
if(ch[i][j]) board[i][j] = ' ';
}
}
// 터트릴 블록들은 true로 표시함
for(int i=h-1; i>=0; i--){
for(int j=0; j<w; j++){
if(board[i][j]==' '){
for(int a=i-1; a>=0; a--){
if(a<0) break;
if(board[a][j]!=' '){
board[i][j] = board[a][j];
board[a][j] = ' ';
break;
}
}
}
}
}
return score;
}
int solution(int m, int n, vector<string> board) {
h = m, w = n;
int answer = 0, temp = 0;
while(true){
temp = friends(board);
answer += temp;
if(temp==0) break;
}
return answer;
}