-
백준(BOJ) 11559번 Puyo Puyo알고리즘 풀이/백준(Boj) 2020. 4. 8. 17:05
문제 : https://www.acmicpc.net/problem/11559
11559번: Puyo Puyo
현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.)
www.acmicpc.net
풀이 :
1.BFS를 통해 4 이상이 되는 모든 알파벳들은 v 배열에 담아주게 되고 '.'을 만든다.
2. 알파벳들을 밑으로 내리고 내릴 알파벳이 없다면 종료하고 있다면 1. 을 반복한다.
코드(C ++)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstring> using namespace std; char a[12][6]; const int dy[4] = { 1,-1,0,0 }; const int dx[4] = { 0,0,1,-1 }; vector<pair<int, int>> v; int bfs(int y, int x, char alp) { int d[12][6]; memset(d, -1, sizeof(d)); queue<pair<int, int>> q; v.push_back({ y,x }); q.push({ y,x }); d[y][x] = 0; int cnt = 1; while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); for (int k = 0; k < 4; ++k) { int ny = y + dy[k]; int nx = x + dx[k]; if (!(0 <= ny && ny < 12 && 0 <= nx && nx < 6)) continue; if (a[ny][nx] != alp) continue; if (d[ny][nx] != -1) continue; v.push_back({ ny,nx }); q.push({ ny,nx }); d[ny][nx] = d[y][x] + 1; cnt += 1; } } return cnt; } int main() { for (int i = 0; i < 12; ++i) for (int j = 0; j < 6; ++j) cin >> a[i][j]; int count = 0; while (1) { bool remov = false; for (int i = 11; i >= 0; --i) { for (int j = 0; j < 6; ++j) { if (a[i][j] == '.') continue; v.clear(); if (bfs(i, j, a[i][j]) >= 4) { for (int z = 0; z < v.size(); ++z) { int y = v[z].first; int x = v[z].second; a[y][x] = '.'; } remov = true; } } } if (remov) count++; bool stopCheck = false; // 모든 알파벳들을 밑으로 내린다 for(int i=11; i >=0; --i) for (int j = 0; j < 6; ++j) { if (a[i][j] == '.') continue; int y = i, x = j; while (y < 11) { if (a[y + 1][x] == '.') { swap(a[y + 1][x], a[y][x]); stopCheck = true; y = y + 1; } else break; } } if (!stopCheck) break; } cout << count << "\n"; return 0; } '알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 16638번 괄호 추가하기 2 (0) 2020.04.09 백준(BOJ) 1726번 로봇 (0) 2020.04.08 백준(BOJ) 17142번 연구소 3 (0) 2020.03.31 백준(BOJ) 1938번 통나무 옮기기 (0) 2020.03.30 백준(BOJ) 18809번 Gaaaaaaaaaarden (0) 2020.03.28