문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/17679
카카오 블라인드 코딩테스트 2018년도 문제.
코딩테스트 리뷰를 보니까 난이도 상 문제였다.
문제 핵심 및 풀이
해당 문제는 제한사항에서 완전탐색으로 가능하다는 것을 인지해야 한다.
핵심적인 구현은 2가지가 있다.
1. 2x2에 연결되어 있는 다른 2x2 블록이 같이 터질 수 있도록 하는 것.
2. 블록이 터진 후 비어있는 공간에 위에 있는 블록들이 떨어지는 것.
2x2 블록들이 연쇄적으로 사라지게 하기
일단 2x2 조건을 만족하는 블록들을 찾아내는 것은 쉽다.
무조건 2x2 고정이기 때문에 현재 좌표를 (i, j)라고 한다면
( i , j ) == ( i , j+1 ) == ( i+1 , j+1) == ( i+1 , j)
이것만 확인하면 된다.
문제는 같은 블록들이 이어져있는 것을 연쇄적으로 터트리는 것.
이건 맵의 크기가 최대 30x30까지밖에 되지 않기 때문에
전체 맵을 탐색 하면서, 조건을 만족하는 2x2 블록을 찾고
마지막까지 탐색 한 뒤에 동시에 없애면 된다.
문제에 나와있는 얘시로 설명하자면 이렇다.
이 그림을 보면 2x2 블록인 A가 두 개 겹쳐있는 것을 확인할 수 있다.
정상적으로 되려면 7개의 A가 없어져야 한다.
그런데 만약 탐색을 하는 과정에서, 2x2블록을 발견하고 그 즉시 없앴다고 해보자.
그럼 다음 탐색에서는 원래는 2x2 블록이지만 A 블록을 인식할 수 없게 된다.
그래서 모든 블록을 찾은 후에
한 번에 2x2 블록들을 터트려야 하는 것이다.
블록이 떨어지는 것을 구현
블록이 떨어지는 것을 구현하기 전에,
해당 공간이 빈 공간이라는 것을 표시하기 위해, 터진 공간을 '0'으로 문자를 바꾸었다.
블록이 위에서 아래로만 떨어지는 것이기 때문에, 이를 스택을 이용하여 구현하였다.
스택을 사용하여 빈 공간인 '0'를 제외하곤 같은 열(세로)에 있는 것을
모두 넣고 빼는 것을 반복한다.
그렇게 하면 자연스럽게 블록들이 빈 공간 없이 아래에서부터 쌓이게 된다.
위와 같이 6개의 스택을 만든 뒤에,
'0'을 제외하곤 각각의 큐에 넣은 뒤 다시 밑에서부터 쌓는다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <stack>
using namespace std;
char map[30][30]; // 전체 맵 크기
// 중복으로 삭제 리스트에 들어가는 것을 방지하기 위해
bool visited[30][30] = {false,};
// 좌표 구조체
struct Point{
int x;
int y;
};
// 2x2 블록인지 확인
bool isSquare(int x, int y){
if(map[x][y] == '0') return false; // 0인 경우 제외
return (map[x][y] == map[x][y+1]
&& map[x][y] == map[x+1][y+1]
&& map[x][y] == map[x+1][y]);
}
// 전체 탐색
int search(int m, int n){
// 2x2 방향 모두 검사
int dx[] = {0,0,1,1};
int dy[] = {0,1,1,0};
vector<Point> v; // 삭제할 좌표를 담아둘 벡터
// 2x2이기 때문에 배열 밖으로 나가는 것을 조심
for(int i = 0; i < m-1; i++){
for(int j = 0; j < n-1; j++){
// 2x2 블록이라면
if(isSquare(i,j)){
// 각각의 칸이 이미 vector에 들어있는지 확인
// 확인은 visited을 통해 확인
for(int k = 0; k < 4; k++){
int x = i+dx[k];
int y = j+dy[k];
if(!visited[x][y]){
visited[x][y] = true;
v.push_back({x,y});
}
}
}
}
}
// 삭제 리스트들을 모두 삭제
for(auto it : v){
int x = it.x;
int y = it.y;
map[x][y] = '0'; // 0으로 만들어줌
}
return v.size(); // 반환 값은 삭제한 개수
}
// 떨어지는 것을 구현한 함수 (size -> 행의 크기, y -> 열의 위치)
void drop(int size, int y){
stack<char> s;
// '0'을 제외하고선 모두 벡터에 담음
for(int i = 0; i < size; i++){
if(map[i][y] == '0') continue;
s.push(map[i][y]);
}
// 맨 아래서부터 하나씩 채움
for(int i = size-1; i >= 0; i--){
// 스택에 비어있지 않으면 가장 위에있는걸로
if(!s.empty()){
map[i][y] = s.top();
s.pop();
}
// 비어있으면 공백으로 채움
else map[i][y] = '0';
}
}
int solution(int m, int n, vector<string> board) {
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[i].size(); j++) map[i][j] = board[i][j];
}
int pre = -1;
int answer = 0;
// 이전 개수와 현재 개수가 같다면 더이상 삭제할게 없는 것
while(answer != pre){
pre = answer;
answer += search(m,n);
for(int i = 0; i < n; i++){
drop(m,i);
}
// 다시 시뮬레이션을 하기 위해 visitd배열 초기화
fill(&visited[0][0],&visited[m-1][n],false);
}
return answer;
}↑
Java 구현 코드
↓
import java.util.*;
class Solution {
// 좌표를 나타내는 클래스 Point
class Point{
int x,y;
// 생성자
Point(int x, int y){
this.x = x;
this.y = y;
}
// equals 오버라이딩을 통해 x와 y값이 같으면 동일한 것으로 설정한다.
@Override
public boolean equals(Object obj){
Point p = (Point)obj;
return (this.x == p.x) && (this.y == p.y);
}
}
char[][] map; // 전체 맵
// 전체 맵을 탐색하는 함수
public int search(){
List<Point> delList = new ArrayList<>(); // 삭제할 블록의 좌표를 리스트에 넣는다.
//전체 맵 탐색
// 인덱스밖으로 벗어나는 것을 방지하기 위해 2x2 블록에 맞춰 끝점을 잡는다.
for(int i = 0; i < map.length-1; i++){
for(int j = 0; j < map[i].length-1; j++){
// 해당 좌표를 기준으로 한 2x2가 조건에 만족할 때
if(isSquare(i,j)){
// 해당 블록들이 delList에 있는지 확인하고 없으면 넣는다. (중복 방지)
if(!delList.contains(new Point(i,j))) delList.add(new Point(i,j));
if(!delList.contains(new Point(i,j+1))) delList.add(new Point(i,j+1));
if(!delList.contains(new Point(i+1,j+1))) delList.add(new Point(i+1,j+1));
if(!delList.contains(new Point(i+1,j))) delList.add(new Point(i+1,j));
}
}
}
// 삭제리스트에서 좌표를 찾아 '0'으로 만든다.
for(Point del : delList){
int x = del.x;
int y = del.y;
map[x][y] = '0';
}
return delList.size(); // 리턴하는 것은 삭제 리스트의 개수
}
// 해당 2x2가 조건을 만족하는지 확인
public boolean isSquare(int x, int y){
return ((map[x][y] == map[x][y+1])
&& (map[x][y] == map[x+1][y+1])
&& (map[x][y] == map[x+1][y]
&& (map[x][y] != '0')));
}
// 스택을 이용해 떨어뜨리는 함수(y -> 몇번째 스택에 해당하는가)
public void drop(int y){
Stack<Character> stack = new Stack<>();
// 해당 줄을 0을 제외하곤 다 스택에 순서대로 넣는다.
for(int i = 0; i < map.length; i++){
if(map[i][y] == '0') continue;
stack.push(map[i][y]);
}
int idx = map.length-1; // 가장 밑에서부터 쌓기 위해
// 맵 밑에서부터 하나씩 채운다.
for(int i = map.length-1; i >= 0; i--){
if(!stack.empty()){
map[idx][y] = stack.pop();
}
// 다 채우고 stack이 비어있다면 나머지는 0으로 채움
else map[idx][y] = '0';
idx--;
}
}
public int solution(int m, int n, String[] board) {
int answer = 0;
int pre = -1;
map = new char[m][n];
for(int i = 0; i < board.length; i++){
char[] arr = board[i].toCharArray();
for(int j = 0; j < arr.length; j++){
map[i][j] = arr[j];
}
}
// 이전 개수와 현재 개수가 같다면 삭제할 게 더이상 없는 것
while(pre != answer){
pre = answer;
answer += search();
for(int i = 0; i < map[0].length; i++) drop(i);
}
return answer;
}
}↑
시행착오
너무 어렵게 접근했다. bfs로 접근하다 보니 오히려 더 어려워진 것 같다.
좀 직관적으로 푸는 연습을 해봐야 할 것 같다. 너무 어렵게만 보는 것 같다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me