[백준] Puyo Puyo

출처:: https://www.acmicpc.net/problem/11559

분류:: BFS

 

1. 문제 이해 및 해결과정

 

1번 풀이 (c++) 1. 입력받음 string 으로 2. 전체 탐색하면서 (bfs) 같은 것의 개수가 4개이상이면 bomb = true    2-1) 탐색하면서 4개이상인 것은 . 으로 바꿈  3. bomb가 true이면 1증가, 하고 fall떨어뜨려야해 4. bomb가 false면 끝

 

2번 풀이 (python) 1. 4개 이상의 블록이 인접해 있으면 . 으로 바꿈 2. 현재 보드에서 블록을 모두 처리 한 후 , fall 떨어뜨리는 것 처리함

 

2. 풀이방법

1. c++

#if 01
//Puyo Puyo
//https://www.acmicpc.net/problem/11559
#include <iostream>
#include <queue>
#include <cstring> //memset
#define r 12
#define c 6
using namespace std;

char map[r + 2][c + 2];
int visited[r + 2][c  + 2];
int dh[] = { -1,1,0,0 }; //상하좌우
int dw[] = { 0,0,-1,1 };


void fall() {
	for (int j = 0; j < c; j++) {
		for (int i = r - 1; i >= 0; i--) {
			if (map[i][j] == '.')continue;
			for (int k = r - 1; k >= i; k--) {
				if (map[k][j] == '.') {
					map[k][j] = map[i][j];
					map[i][j] = '.';
				}
			}
		}
	
	}

}
int BFS(int h,int w,char ch) { 
	//1. 초기화
	queue < pair < int, int> > q;
	vector <pair < int, int> > block;

	//2. 시작점 넣기
	q.push({ h,w });
	block.push_back({ h,w });
	visited[h][w] = 1;

	//3. 반복문
	while (!q.empty()) {
		pair < int, int > cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nh = cur.first + dh[i];
			int nw = cur.second + dw[i];
			
			if (nh < 0 || nh >= r || nw < 0 || nw >= c)continue;
			if (map[nh][nw] == ch && visited[nh][nw] == 0) {
				q.push({ nh,nw });
				block.push_back({ nh,nw });
				visited[nh][nw] = 1;
			}
		}
	
	}

	//4. 결과
	if (block.size() >= 4) {
		for (auto i : block) {
			map[i.first][i.second] = '.'; //뿌요되는 것 .로
		}
		return 1;
	}

	return 0;
}
bool bomb() {
	
	bool flag = false;

	memset(visited, 0, sizeof(visited));
	for (int i = r - 1; i >= 0; i--) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] == '.' || visited[i][j] == 1) continue;
				
				if (BFS(i, j, map[i][j]) == 1) { 
					flag = true;
				}
		
		}
	}


	return flag;
}
void Solve() {
	int sol=0;

	while (bomb()) {
		fall();
		sol += 1;
	}
	cout << sol;
}
void InputData() {

	for (int i = 0; i < r; i++) {
		scanf("%s",&map[i][0]);
	}
}

int main() {


	freopen("input.txt", "r", stdin);
	InputData();
	Solve();
	
	return 0;
}
#endif

2. python

#Puyo Puyo
#https://www.acmicpc.net/problem/11559
import sys
from collections import deque
sys.stdin = open("input.txt","r")
board=[list(input()) for _ in range(12)]
dh=[-1,1,0,0]
dw=[0,0,-1,1]
q=deque()

def fall():
    for w in range(6): #열
        for h in range(11, -1, -1): #행
            if board[h][w] == '.': continue #아래서 부터 for문 돌면서 문자인 곳에서 stop
            for k in range(11, h, -1): #board[x][y]가 알파벳이고 board[k][y]가 . 이면
                if board[k][w] == '.':
                    #print(h, k,board[h][w],board[k][w])
                    board[k][w] = board[h][w]
                    board[h][w] = '.'


def bfs(h,w):
    q.append((h,w))
    block=[(h,w)] #블럭 담아두기
    visited[h][w]=True
    color = board[h][w] #현재색깔
    while q:
        curh,curw=q.popleft()
        for i in range(4):
            nh=curh+dh[i]
            nw=curw+dw[i]
            if nh<0 or nh>=12 or nw<0 or nw>=6 or visited[nh][nw]==True:
                continue
            if board[nh][nw]==color:
                q.append((nh,nw))
                block.append((nh,nw))
                visited[nh][nw] = True
    if len(block)>=4:
        for i,j in block:
            board[i][j]='.' #터뜨리기
        return True
    else:
        return False

cnt=0
while True:
    flag = False
    visited=[[False]*6 for _ in range(12)]
    for i in range(11,-1,-1):
        for j in range(0,5):
            if board[i][j]!='.' and visited[i][j]==False:
                if bfs(i,j):
                    flag=True
  
    fall()
    if flag==False:
        break
    else:
        cnt+=1

print(cnt)

 

3. 오답원인

-solve와 bomb를 합치면 안된다. bomb할 것이 있을때까지 니까 

-큐와 현재 터지는 블럭을 저장하는 벡터는 STATIC으로 선언하면안되고 BFS탐색 시작할 때 새로 생겨야함

-> 누적되지않기 위해 

 

4. 알게된 점

-memset => #include <cstring> 필요함, memset(visited,0,sizeof(visited))

fall() : 떨어뜨리는 것 처리하는 코드 

def fall():
    for w in range(6): #열
        for h in range(11, -1, -1): #행
            if board[h][w] == '.': continue #아래서 부터 for문 돌면서 문자인 곳에서 stop
            for k in range(11, h, -1): #board[x][y]가 알파벳이고 board[k][y]가 . 이면
                if board[k][w] == '.':
                    board[k][w] = board[h][w]
                    board[h][w] = '.'