[BEAKJOON] 11559_puyo puyo(뿌요뿌요)_C언어

SW 업무 관련/백준

[BEAKJOON] 11559_puyo puyo(뿌요뿌요)_C언어

WillBe_ 2017. 9. 8. 20:09

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


풀이


1. 같은 문자가 4개 이상으로 뭉쳐져 있는 곳들을 BFS를 통해 찾아 없앤다.

없을경우 탐색을 종료.

-> 처음에 DFS로 찾았는데 ㅗ 모양은 제거 못 하더라..ㅎㅎ생각해보면 당연함. 내가 잘못 생각하는 것 일수도 있고.


2. 연쇄 ++;


3. 중력으로 문자들이 아래로 떨어진다~~~


4. 1로 다시 돌아간다. 



여기서 중요한건!!!!!!!!!!!!!!!!

중력으로 문자들이 떨어질 때 문자들을 없애는 동작이 1회라는 거나..나는 예로 4개 이상의 R을 없애고 +1, Y를 없애고 +1을 하였는데,

이렇게 하는게 아니라 R, Y를 모두 없앤 후 +1이다.



제출한 코드

(코드상에 약간 이상한 부분이 있으나..왜 그런지 몰라 고민중이다. 그래도 정답이니깐 일단 올린다. 만약 내가 처음에 생각한데로 R없애고 +1, Y없애고 +1 이런 식이면 틀릴 것 이다.)


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
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <string.h>
char map[14][10];
int map_check[14][10];
int Q_y[1000], Q_x[1000], Q_front = -1, Q_back = -1;
int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 };
int answer;
////////////////////////////////////////////////////////////////////////////
void gravity(int y, int x, char CH)//문자를 내린다
{
    map[y][x] = '.';
 
    while (1)
    {
        y++;
        if (y == 12 || map[y][x] != '.')
            break;
    }
    map[y - 1][x] = CH;
}
 
void search_2()//내려야될 문자를 찾는다
{
    for (int i = 0; i < 6; i++)
    {
        for (int j = 11; j >= 0; j--)
        {
            if (map[j][i] != '.')
                gravity(j, i, map[j][i]);
        }
    }
}
///////////////////////////////////////////////////////////////////////////
int fc(int y, int x, char CH)//4개 이상이면 지워요~
{
    int num = 1;
    int flag = 0;
    memset(Q_x, 0sizeof(Q_x));
    memset(Q_y, 0sizeof(Q_y));
    memset(map_check, 0sizeof(map_check));
    Q_front = Q_back = -1;
 
    Q_x[++Q_back] = x;
    Q_y[Q_back] = y;
 
    while (Q_front != Q_back)
    {
        int xx = Q_x[++Q_front];
        int yy = Q_y[Q_front];
        map_check[yy][xx] = 1;
 
        for (int i = 0; i < 4; i++)
        {
            int xxx = xx + dx[i];
            int yyy = yy + dy[i];
 
            if (xxx < 0 || yyy < 0 || xxx>5 || yyy>12 || map_check[yyy][xxx])
                continue;
 
            if (map[yyy][xxx] == CH)
            {
                Q_x[++Q_back] = xxx;
                Q_y[Q_back] = yyy;
                num++;
            }
        }
    }
 
    //printf("/////////// %d   /    %d %d  \n",Q_back, Q_y[0],Q_x[0]);
    if (num >= 4)
    {
        for (int i = 0; i <= Q_back; i++)
        {
            map[Q_y[i]][Q_x[i]] = '.';
        }
        flag = 1;
    }
    return flag;
}
 
int search()//뒤져뒤져~
{
    int flag = 0, F = 0;
    for (int i = 11; i >= 0; i--)
    {
        for (int j = 0; j < 6; j++)
        {
            if (map[i][j] != '.')
            {
                flag += fc(i, j, map[i][j]);
            }
        }
    }
    if (flag)
        answer++;
 
    return flag;
}
 
int main()
{
    int temp = 0;
    for (int i = 0; i < 12; i++)
        scanf("%s", map[i]);
 
    search();
    search_2();
    while (temp<12*6)
    {
        search();
        search_2();
        temp++;
    }
 
    printf("%d\n", answer);
 
    return 0;
}
cs