문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/colored-bomb/description?page=1&pageSize=20
💻 문제 풀이 : C++
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#define MAX_SIZE 25
#define EMPTY -2
#define STONE -1
#define RED 0
using namespace std;
struct Coord {
int r, c;
};
struct Bundle {
int idx;
int num;
int rednum;
priority_queue<Coord> s;
};
int N, M;
int MAP[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };
priority_queue<Bundle> bundle;
Bundle tmp;
vector<Coord> red;
// 폭탄 꾸러미 우선순위
bool operator<(Bundle a, Bundle b)
{
// 폭탄 개수 많을수록
if (a.num < b.num) return true;
if (a.num > b.num) return false;
// 빨간 폭탄 적을수록
if (a.rednum > b.rednum) return true;
if (a.rednum < b.rednum) return false;
if (a.s.size() == 0 || b.s.size() == 0) return false;
// 기준점 행 클수록
if (a.s.top().r < b.s.top().r) return true;
if (a.s.top().r > b.s.top().r) return false;
// 기준점 열 작을수록
if (a.s.top().c > b.s.top().c) return true;
if (a.s.top().c < b.s.top().c) return false;
return false;
}
// 기준점 폭탄 우선순위
bool operator<(Coord a, Coord b)
{
// 폭탄 중 빨간색이 아니면서
if (MAP[a.r][a.c] == RED) return false;
if (MAP[b.r][b.c] == RED) return false;
// 행이 가장 큰 칸
if (a.r < b.r) return true;
if (a.r > b.r) return false;
// 열이 가장 작은 값
if (a.c > b.c) return true;
if (a.c < b.c) return false;
return false;
}
int inRange(Coord s)
{
int r = s.r;
int c = s.c;
if (r < 0 || c < 0 || r >= N || c >= N) return 0;
else return 1;
}
void bundleClear(int idx)
{
tmp.idx = idx;
tmp.rednum = 0;
tmp.num = 0;
while (!tmp.s.empty()) tmp.s.pop();
}
void bombClear(int idx)
{
Bundle tmp = bundle.top();
while (!tmp.s.empty())
{
int r = tmp.s.top().r;
int c = tmp.s.top().c;
MAP[r][c] = EMPTY;
tmp.s.pop();
}
}
// 묶음 찾기
void search(Coord s, int idx)
{
queue<Coord> nowQ;
nowQ.push(s);
int color = MAP[s.r][s.c];
while (!nowQ.empty())
{
Coord now = nowQ.front();
nowQ.pop();
for (int i = 0; i < 4; i++)
{
Coord next = { now.r + dr[i], now.c + dc[i] };
// 범위를 벗어난 경우
if (!inRange(next)) continue;
// 색이 다른 경우
if (color != MAP[next.r][next.c]
&& MAP[next.r][next.c] != RED) continue;
// 돌인 경우
if (MAP[next.r][next.c] == STONE) continue;
// 이미 방문한 경우
if (visited[next.r][next.c] != 0) continue;
visited[next.r][next.c] = idx;
tmp.num += 1;
if (MAP[next.r][next.c] == RED) tmp.rednum += 1;
tmp.s.push(next);
nowQ.push(next);
}
}
}
// 반시계방향 회전
void rotate()
{
int TMP[MAX_SIZE][MAX_SIZE];
memset(TMP, 0, sizeof(TMP));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
TMP[i][j] = MAP[j][N - 1 - i];
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
MAP[i][j] = TMP[i][j];
}
}
}
// 중력
void gravity()
{
// 매 열을 탐색
for (int c = 0; c < N; c++)
{
queue<int> newArr;
int bottom = N - 1;
while (bottom > 0)
{
int r = bottom;
while (MAP[r][c] != STONE && r >= 0)
{
if (MAP[r][c] != EMPTY)
newArr.push(MAP[r][c]);
r--;
}
for (int k = bottom; k > r; k--)
{
if (!newArr.empty())
{
MAP[k][c] = newArr.front();
newArr.pop();
}
else {
MAP[k][c] = EMPTY;
}
}
bottom = r - 1;
}
}
}
void CLEAR()
{
}
void INPUT()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> MAP[i][j];
}
}
}
void SOLVE()
{
int score = 0;
int time = 0;
while (time < 10000)
{
red.clear();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (MAP[i][j] == RED)
red.push_back({ i, j });
}
}
memset(visited, 0, sizeof(visited));
while (!bundle.empty()) bundle.pop();
int idx = 1;
// 폭탄 묶음 선택
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
if (MAP[r][c] == EMPTY || MAP[r][c] == STONE || MAP[r][c] == RED) continue;
// 매 탐색마다 빨간폭탄은 탐색 초기화!!!
for (int k = 0; k < red.size(); k++)
{
visited[red[k].r][red[k].c] = 0;
}
if (visited[r][c] != 0) continue;
visited[r][c] = idx;
bundleClear(idx);
tmp.num += 1;
tmp.s.push({ r, c });
search({ r, c }, idx);
if (tmp.num != 1) {
bundle.push(tmp);
}
idx += 1;
}
}
// 더 이상 폭탄 묶음이 없으면
if (idx == 1 || bundle.empty()) break;
// 폭탄 제거
idx = bundle.top().idx;
score += (bundle.top().num * bundle.top().num);
bombClear(idx);
// 폭탄 중력
gravity();
// 격자 판 반시계방향 회전
rotate();
// 폭탄 중력
gravity();
time++;
}
cout << score << endl;
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
}
📌 memo 😊
✔️ 우선순위 조건 중 한 가지를 놓쳐 오랜 시간 헤맸다.
(기준점 폭탄은 빨간색이 아니다!)
- 구현 문제에서 우선순위를 고려해야 하는 경우, 조건을 빼먹지 않도록 문제를 "꼼꼼히" 봐야할 것!
✔️ C++의 std 우선순위 큐 (priority queue)에서 operator로 우선순위를 정하는 경우에 "<" 연산자의 활용만이 가능하다. 이때, 이는 직관적인 우선순위와 반대임을 주의해야 한다.
- 행이 큰 폭탄의 우선순위를 더 높게하자!
if (bomb_a.r < bomb_b.r) return true;
if (bomb_a.r > bomb_b.r) return false;마치 행이 작은 폭탄의 우선순위가 높은 것처럼 보인다.
그러나 기준 연산자가 " < " 임에 주의할 것!
공부방