Implementation BFS
상어 중학교
풀이과정
상어 초등학교 문제와 마찬가지로 우선순위 큐를 이용해 구현하였다.
1. 크기가 가장 큰 블록 찾기(BFS) -> find_block()
2. 중력 적용 -> down()
3. 90도 반시계 방향 회전 -> rotate()
4. 중력 적용 -> down()
위의 문제 요구사항대로 차근차근 구현만 해주면 쉽게 끝난다.
여기서 헷갈릴만한 부분은 크게 두 가지가 있는 것 같다.
(1) BFS시 무지개 블록 방문 처리
가장 큰 블록을 찾을 때 방문하는 visit 배열에서 무지개 블록을 처리하면 안된다. 나는 새로운 블록 그룹을 만날때마다 bool rainbowVisit[20][20]라는 visit 배열을 새로 만들어주었다.
(2) 우선순위 큐 구현
나는 내 맘대로 info라는 구조체를 만들고 비교함수를 구현했다.
struct info {
int x, y, cnt = 0, rainbowCnt = 0;
bool operator<(const info& i) const {
if (cnt == i.cnt) {
if (rainbowCnt == i.rainbowCnt) {
if (x == i.x) return y < i.y;
else return x < i.x;
}
else return rainbowCnt < i.rainbowCnt;
}
else return cnt < i.cnt;
}
};
근데 상어 초등학교 문제도 그렇고 이 문제도 그렇고 tuple<int,int,int,int>을 이용하는 사람이 많더라. tuple은 두 가지의 변수만 저장할 수 있는 pair와 달리 저장할 수 있는 변수에 제한이 없다고 한다. 비교함수도 구현되어있어서 상어중학교같이 비교함수가 간단한 문제의 경우 적극 활용하면 좋을것 같다!
1. 크기가 가장 큰 블록
2. 무지개 개수가 많은 블록
3. 행이 큰 블록
4. 열이 큰 블록
현재 문제 조건에서는 pQ.push({cnt, rainbowCnt, x, y})로 해주면 되고, 여기서 만약 3번 조건이 행이 작은 블록이라면 pQ.push({cnt, rainbowCnt, -x, y}) 이런식으로 작성해서 사용하면 유용할 것 같다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define x first
#define y second
#define BLANK -2
struct info {
int x, y, cnt = 0, rainbowCnt = 0;
bool operator<(const info& i) const {
if (cnt == i.cnt) {
if (rainbowCnt == i.rainbowCnt) {
if (x == i.x) return y < i.y;
else return x < i.x;
}
else return rainbowCnt < i.rainbowCnt;
}
else return cnt < i.cnt;
}
};
int res = 0;
int N, M;
int board[20][20];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
void input();
bool find_block(); //블록 찾기
void down(); //중력 작용
void rotate(); //반시계 회전
int main() {
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
input();
while (true) {
int ret = find_block();
if (!ret) break; //블록이 없는 경우 종료
down();
rotate();
down();
}
cout << res << '\n';
return 0;
}
void input() {
//freopen("input.txt", "r", stdin);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
}
bool find_block() {
bool visit[20][20] = { false, };
priority_queue<info> pQ;
// 블록을 찾아 priority queue에 삽입
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] > 0 && !visit[i][j]) {
bool rainbowVisit[20][20] = { false, };
queue<pair<int,int>> Q;
Q.push({ i,j });
visit[i][j] = true;
int cnt = 1, rainbowCnt = 0;
while (!Q.empty()) {
int x = Q.front().x;
int y = Q.front().y;
Q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx<0 || nx>N - 1 || ny<0 || ny>N - 1
|| visit[nx][ny] || rainbowVisit[nx][ny]) continue;
if (board[nx][ny] == 0) {
rainbowVisit[nx][ny] = true;
Q.push({ nx,ny });
cnt++;
rainbowCnt++;
}
else if (board[i][j] == board[nx][ny]) {
visit[nx][ny] = true;
Q.push({ nx,ny });
cnt++;
}
}
}
pQ.push({ i,j,cnt, rainbowCnt });
}
}
}
// 더 이상 삭제할 블록이 없는 경우 false를 반환하고 main 함수 종료
if (pQ.empty()) return false;
// 가장 큰 블록 찾기
int x = pQ.top().x;
int y = pQ.top().y;
int cnt = pQ.top().cnt;
if (cnt < 2) return false;
res += cnt * cnt;
// 블록 삭제 작업 -> 삭제된 블록에는 BLANK(-2) 넣기
queue<pair<int, int>> Q;
Q.push({x,y });
int blockId = board[x][y];
board[x][y] = BLANK;
while (!Q.empty()) {
int x = Q.front().x;
int y = Q.front().y;
Q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx<0 || nx>N - 1 || ny<0 || ny>N - 1) continue;
if (board[nx][ny] == 0 || board[nx][ny]== blockId) {
Q.push({ nx,ny });
board[nx][ny] = BLANK;
}
}
}
return true;
}
void down() {
for (int i = 0; i < N; i++) {
for (int j = N - 1; j >= 0;j--) {
if (board[j][i] == BLANK) {
int x = j;
int y = i;
while (x > 0 && board[x][y]==BLANK) x--;
if (board[x][y] == -1) continue;
board[j][i] = board[x][y];
board[x][y] = BLANK;
}
}
}
}
void rotate() {
int tempBoard[20][20];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
tempBoard[i][j] = board[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = tempBoard[j][N-1-i];
}
}
}
결과
