반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 구현


구현을 요구하는 문제이다.


vcR~vcY는 각각 현재 컬러들의 위치를 저장해주는 역할이고 그 아래에서 bfs를 통해 각 컬러의 위치마다 4개이상 터지는지 확인하고 있다.


그 후 재정렬을 하게 되는데 이 부분에서 조금 더 최적화 할 수 있지만 충분히 통과할 수 있기에


위에서부터 아래로보며 밑으로 한칸씩 내릴 수 있다면 계속해서 내려주는 방식을 이용하였다.






소스 코드 : 


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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <cstdio>
#include <queue>
#include <memory.h>
#include <vector>
 
using namespace std;
 
typedef pair<int, int> pii;
 
char arr[13][7];
bool visit[13][7];
 
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };
 
vector<pii> getColor(char color)
{
    vector<pii> vc;
    for (int i = 0; i < 12; i++)
        for (int j = 0; j < 6; j++)
            if (arr[i][j] == color)
                vc.push_back({ i,j });
 
    return vc;
}
 
bool bfs(char color, vector<pii> vc)
{
    queue<pii> q;
    bool chk = false;
 
    for (int i = 0; i < vc.size(); i++)
    {
        int y = vc[i].first;
        int x = vc[i].second;
 
        q.push({ y,x });
        int cnt = 0;
        memset(visit, 0, sizeof(visit));
 
        while (!q.empty())
        {
            int hy = q.front().first;
            int hx = q.front().second;
            
            q.pop();
 
            if (visit[hy][hx])
                continue;
 
            visit[hy][hx] = true;
            cnt++;
            for (int j = 0; j < 4; j++)
            {
                int ny = hy + dy[j];
                int nx = hx + dx[j];
 
                if ((0 <= ny && ny < 12 && (0 <= nx && nx < 12)) && arr[ny][nx] == color)
                    q.push({ ny,nx });
            }
 
        }
 
        if (cnt >= 4)
        {
            for (int i = 0; i < 12; i++)
                for (int j = 0; j < 6; j++)
                    if (visit[i][j])
                    {
                        arr[i][j] = '.';
                        chk = true;
                    }
        }
    }
 
    if (chk)
        return true;
    else
        return false;
}
 
int main()
{
    for (int i = 0; i < 12; i++)
        scanf("%s", arr[i]);
 
    int combo = 0;
 
    while (1)
    {
        bool isEvent = false;
 
        vector<pii> vcR = getColor('R');
        vector<pii> vcG = getColor('G');
        vector<pii> vcB = getColor('B');
        vector<pii> vcP = getColor('P');
        vector<pii> vcY = getColor('Y');
 
        bool r = bfs('R', vcR);
        bool g = bfs('G', vcG);
        bool b = bfs('B', vcB);
        bool p = bfs('P', vcP);
        bool y = bfs('Y', vcY);
 
        if (r || g || b || p || y)
            isEvent = true;
 
        if (isEvent)
            combo++;
        else
            break;
 
        // 재정렬
        for(int t = 0; t < 12; t++)
            for (int i = 0; i < 12; i++)
            {
                for (int j = 0; j < 6; j++)
                {
                    if (arr[i][j] != '.' && arr[i + 1][j] == '.')
                    {
                        arr[i + 1][j] = arr[i][j];
                        arr[i][j] = '.';
                    }
                }
            }
    }
 
    cout << combo << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[5670번] 휴대폰 자판  (0) 2018.01.26
[13458번] 시험 감독  (2) 2018.01.26
[4963번] 섬의 개수  (0) 2018.01.24
[2667번] 단지번호붙이기  (0) 2018.01.24
[12913번] 매직 포션  (0) 2018.01.23

티스토리툴바