문제 설명
프렌즈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
|
예제에 대한 설명
입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.
출처: https://programmers.co.kr/learn/courses/30/lessons/17679
나의 풀이:
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
set<pair<int, int>>sameBlocks; //2X2내의 좌표 저장(중복X)
bool compare(pair<int, int > a, pair<int, int>b) {
return a.second > b.second;
}
void putCoordinates(int x, int y) { //set에 4개의 좌표 첨가
for (int i = x; i < x + 2; i++)
for (int j = y; j < y+2; j++)
sameBlocks.insert({ i,j });
}
bool isHaveSameBlocks(vector<vector<string>>map) {
for (int i = 0; i < map.size() - 1; i++)
{
if (map[i].size() == 0) continue;
for (int j = 0; j < map[i].size() - 1; j++)
{
if (map[i + 1].size() > j + 1)
{
string a = map[i][j];
string b = map[i + 1][j];
string c = map[i][j + 1];
string d = map[i + 1][j + 1];
if (a == b && a == c && a == d) putCoordinates(i, j);
}
}
}
return sameBlocks.size() == 0 ? false : true;
}
int solution(int m, int n, vector<string> board) {
int answer = 0;
vector<vector<string>>map(n, vector<string>(m));//오른쪽으로 90도 회전된 배열
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
map[i][j] = board[m - j - 1][n - i- 1];
while (isHaveSameBlocks(map)) { //같은 블럭이 안 나올 때 까지
vector<pair<int, int>>results(sameBlocks.begin(), sameBlocks.end());
sort(results.begin(), results.end(), compare); //정렬
for (auto it : results) //2X2 블럭 지우기
map[it.first].erase(map[it.first].begin() + it.second );
answer += sameBlocks.size();
sameBlocks.clear();
}
return answer;
}
처음에 문제를 읽고, 빈칸을 빈칸이 아닌 칸과 교체하는 방식으로 할까 하다가
배열을 오른쪽으로 90도 회전하는 좋은 아이디어가 떠올랐다!
배열을 오른쪽으로 회전하면 vector에서 erase할 때, 자동으로 뒤에 칸의 원소가 앞으로 당겨지기 때문에
지울 때마다 2x2칸 만큼 이동시키는 수고를 덜 수 있을 것이라고 생각했다.
다음 문제 설명 예시의 설명을 통해 이해를 도울 수 있을 것 같다.
▶ 기존의 상태
|
C
|
C
|
B
|
D
|
E
|
|
A
|
A
|
A
|
D
|
E
|
|
A
|
A
|
A
|
B
|
F
|
|
C
|
C
|
B
|
B
|
F
|
👇
|
|
|
|
D
|
E
|
|
|
|
|
D
|
E
|
|
C
|
C
|
B
|
B
|
F
|
|
C
|
C
|
B
|
B
|
F
|
👇
|
|
|
|
|
E
|
|
|
|
|
|
E
|
|
|
|
|
D
|
F
|
|
|
|
|
D
|
F
|
▶ 오른쪽으로 90도 회전
|
C
|
C
|
B
|
D
|
E
|
|
A
|
A
|
A
|
D
|
E
|
|
A
|
A
|
A
|
B
|
F
|
|
C
|
C
|
B
|
B
|
F
|
👇 (90도 회전)
|
F
|
F
|
E
|
E
|
|
B
|
B
|
D
|
D
|
|
B
|
A
|
A
|
B
|
|
C
|
A
|
A
|
C
|
|
C
|
A
|
A
|
C
|
👇
|
F
|
F
|
E
|
E
|
|
B
|
B
|
D
|
D
|
|
B
|
B
|
|
|
|
C
|
C
|
|
|
|
C
|
C
|
|
|
👇
|
F
|
F
|
E
|
E
|
|
D
|
D
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
배열을 돌리는 것 이외에도 고려해야할 사항이 많아서
상당히 긴 시간이 소요된 문제였다..
카카오 코테에서 난이도 '상'으로 출제된 만큼 어려웠다
처음에 코드 채점을 나왔을 때, 시간 초과가 나서 꽤 애먹었다..
isHaveSameBlocks 함수에서 2중 for문의 안쪽 for문에서 문제가 발생했었다.
다음은 수정하기 이전의 isHaveSameBlocks 코드이다.
bool isHaveSameBlocks(vector<vector<string>>map) {
for (int i = 0; i < map.size() - 1; i++)
{
for (int j = 0; j < map[i].size() - 1; j++)
{
if (map[i].size() == 0) continue;
if (map[i + 1].size() > j + 1)
{
string a = map[i][j];
string b = map[i + 1][j];
string c = map[i][j + 1];
string d = map[i + 1][j + 1];
if (a == b && a == c && a == d) putCoordinates(i, j);
}
}
}
return sameBlocks.size() == 0 ? false : true;
}
사실 아직도 이유를 잘 모르겠지만, 배열이 비어있는 경우 map[i].size() == 0 이 되고,
이때 j의 범위는 j < -1 이 되는데, for문에 j++에 됨에 따라 끝나는 것이 아니라
무한히 반복되더라... 0 < -1 이 되는데 왜 안빠져나와지지??!!
쨌든...
if (map[i].size() == 0) continue;
이 문장을 바깥쪽 괄호로 이동시킴으로써 해결하였다.