문제
https://school.programmers.co.kr/learn/courses/30/lessons/17679#
리뷰
문제유형: 구현, 그래프 탐색
실수한 부분
- 블록이 떨어지고 난 뒤
구현 완료 후 2개의 테스트 케이스가 틀려서 해결하지 못한 상태로 그냥 넘어갔었다. 아마 실제 시험이었다면 틀림 처리 당했을 것이다. 내가 실수한 부분은 블록이 '터지고 난 뒤' 위에서 아래로 차곡차곡 쌓이는 부분이다. 바로 위 인덱스로만 덮어씌웠기 때문에, 몇 가지 예제가 틀렸던 것이다. - 2x2 블록을 형성한 부분과 겹침을 허용하면서 2x2 블록을 확인하기
2x2 블록이 다른 2x2 블록과 겹쳐서, 7개 혹은 6개를 만들 수 있었다. 나는 이러한 중복 카운팅을 제거하기 위해, BFS이후 2x2 블록에 해당하는 x, y 좌표들을 벡터 안에 모조리 넣어두고, O(n)의 복잡도로 search 하면서 겹치는지를 확인했다. 매우 비효율적이다. '격자'의 장점을 활용해야 한다.
BFS를 사용하면서 visited[][] 배열을 사용할 테니, 해당 배열을 int 형으로 변경하여 -1 또는 999 정도의 값을 대입하여, '터진다'를 비유적으로 표시할 수 있다. -1 로 표시하기만 하면 블럭들은 2x2에 해당하는 블럭이므로 겹치는지 확인할 필요가 없다(여기서는 주어진 vector<string> board를 수정해도 된다) - BFS 이후, 조건에 맞는 좌표들의 값을 제거해줘야 한다. 이를 위해서 벡터를 사용해 조건에 맞는 x, y 좌표를 다시 꺼내올 수 있으나, 전체 시퀀스 수행 이후 진행해도 되므로, visited[][]를 탐색하는 방식으로도 대체가 가능하다.
핵심
- 블럭 전체 구역 x, y 좌표를 for ++ 하면서 BFS 탐색 진행하기
BFS: 2x2 구역으로 해당 x, y 좌표의 캐릭터와 모두 같은지를 파악.
if yes, visited[][] 혹은 board[][]를 변경하고 다음 x,y 에 대해 2x2를 파악한다.
if no, 그냥 다음으로 넘어간다.
tip, 2x2 를 서치하므로, 마지막 열과 마지막 행은 탐색할 필요가 없다. - 전체 구역을 탐색했으면, '터진다'고 표현한 블럭들을 제거한다(board 직접 수정)
- 빈 공간을 채워넣는다.
채워넣을 때, 인덱스 에러에 주의하자.
해당 행에서 맨 윗 행까지 하나씩 아래로 내리는 작업을 수행하면 된다. 물론, 맨 윗 행은 내려올 것이 없으므로 두 번째 행부터 진행하면 된다.
코드
지저분하지만, 얼마나 못 했는지를 기록으로 남기기 위해 붙여넣는다.
#include <string>
#include <iostream>
#include <vector>
using namespace std;
bool checkblock(int x, int y, vector<string>& board){
char ch = board[x][y];
for(int i=0; i<2; i++){
for(int j=0; j<2; j++){
if(ch != board[x+i][y+j])
return false;
}
}
return true;
}
void change(vector<pair<int, int>>& recordvec, vector<string>& board){
char target = '1';
for(auto iter=recordvec.begin(); iter!=recordvec.end(); iter++)
board[iter->first][iter->second] = target;
recordvec.clear();
}
int record_and_count(int x, int y, vector<pair<int, int>>& recordvec){
int cnt = 4;
for(int i=0; i<2; i++){
for(int j=0; j<2; j++){
bool find_flag = false;
for(auto iter=recordvec.begin(); iter!=recordvec.end(); iter++){
if(iter->first == x+i && iter->second == y+j){
cnt --;
find_flag = true;
break;
}
}
if(!find_flag)
recordvec.push_back({x+i, y+j});
}
}
return cnt;
}
void rebuild(vector<string>& board){
for(int i=1; i<board.size(); i++){
for(int j=0; j<board[i].size(); j++){
if(board[i][j] == '1'){
for(int s=i; s>=1; s--){
board[s][j] = board[s-1][j];
board[s-1][j] = '2';
}
}
}
}
}
int solution(int m, int n, vector<string> board) {
int answer = 0;
vector<pair<int, int>> recordvec;
// 전체 반복용
while(true){
int fourblock = 0;
// 2x2 블록 서치용
for(int i=0; i<board.size()-1; i++){
for(int j=0; j<board[i].size()-1; j++){
char ch = board[i][j];
if(ch != '2' && checkblock(i, j, board)){
fourblock ++;
answer += record_and_count(i, j, recordvec);
//cout << "i, j: " << i << ", " << j << ", " << answer << '\n';
}
}
}
if(fourblock == 0)
break;
// 바꾸고 채워넣기용
change(recordvec, board);
/*
for(int i=0; i<board.size(); i++)
cout << board[i] << '\n';
cout << '\n';
*/
rebuild(board);
/*
for(int i=0; i<board.size(); i++)
cout << board[i] << '\n';
cout << '\n';
*/
}
return answer;
}
비슷한 문제
구현 + 그래프 탐색 문제가 비슷한 유형으로 보인다.
백준 16235 나무 재테크 https://www.acmicpc.net/problem/16235
프로그래머스 카카오프렌즈 컬러링 북 https://school.programmers.co.kr/learn/courses/30/lessons/1829