[백준 11559번] Puyo Puyo

2018. 1. 12. 01:21알고리즘/백준

반응형








소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
using namespace std;
 
/*================================
           문제의 옵션
  1. R,G,B,P,Y 총 5가지 (대문자)
  2. 12*6의 문자가 주어짐
  3. .은 빈공간, 나머지는 뿌요
==================================*/
 
char puyo[13][7];
int v[13][7], q[10001], h, t;
int dx[4= { 00-11 };
int dy[4= { -1100 };
bool isPossibleFlag;
 
/*=====================
      방문 초기화
=======================*/
void visitInit() { // 0 = 미방문, 1 = 방문
    for (int i = 0; i < 12; i++)
        for (int j = 0; j < 6; j++)
            v[i][j] = 0;
}
 
 
/*=====================
      뿌요 내리기
=======================*/
void puyoDown() {
    for (int i = 0; i < 6; i++) {
        for (int j = 11; j >= 0; j--) {
            if (puyo[j][i] != '.') { // 뿌요를 만나면 .을 다시 아래에서부터 검색
                for (int k = 11; k > j; k--) {
                    if (puyo[k][i] == '.') { // 가장 처음으로 만나는 .이랑 교체
                        char tmp = puyo[k][i];
                        puyo[k][i] = puyo[j][i];
                        puyo[j][i] = tmp;
                        break// 더이상 찾지않게
                    }
                }
            }
        }
    }
}
 
 
 
/*=====================
    뿌요 찾아 없애기
=======================*/
void deletePuyo() {
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            if (puyo[i][j] != '.') {  // 뿌요를 찾음.
                char curPuyo = puyo[i][j]; // 현재 뿌요 상태값
                h = 0, t = 0;
                q[t++= i * 100 + j;
                int puyoCnt = 0;
                visitInit();
                while (h != t) {  // BFS로 탐색
                    int pos = q[h++];
                    int x = pos / 100// 위에서 x번째
                    int y = pos % 100// 왼쪽에서 y번째
                    for (int dir = 0; dir < 4; dir++) {
                        int xx = x + dx[dir];
                        int yy = y + dy[dir];
                        if (xx < 0 || xx>11 || yy < 0 || yy>5) { continue; }
                        if (v[xx][yy] == 0 && puyo[xx][yy] == curPuyo) {
                            v[xx][yy] = ++puyoCnt;
                            q[t++= xx * 100 + yy;
                        }
                    }
                }
                // BFS가 끝나고 뿌요 카운트가 4이상이면 큐를 다시 돌면서 해당 뿌요 .으로 변경
                if (puyoCnt >= 4) {
                    h = 0, isPossibleFlag = true;
                    while (h != t) {
                        int pos = q[h++];
                        int x = pos / 100;
                        int y = pos % 100;
                        puyo[x][y] = '.';
                    }
                }
            }
        }
    }
}
 
/*=====================
        메인 함수
=======================*/
int main() {
    int result = 0;
    for (int i = 0; i < 12; i++)
        for (int j = 0; j < 6; j++)
            cin >> puyo[i][j];
    while (1) {
        isPossibleFlag = false;
        deletePuyo();
        puyoDown();
        if (isPossibleFlag==false) { break; }
        else { result++; }
    }
    cout << result << '\n';
    return 0;
}
cs


반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준 2909번] 캔디 구매  (0) 2018.01.12
[백준 2985번] 세 수  (0) 2018.01.12
[백준 3023번] 마술사 이민혁  (0) 2018.01.11
[백준 1748번] 수 이어 쓰기 1  (0) 2018.01.11
[백준 9322번] 철벽 보안 알고리즘  (0) 2018.01.11