반응형
그렇게 깔끔하게 풀진 못해서 조금 아쉽다.
그리고 나는 DFS를 썼는데, 다른분들의 코드를 보니 BFS로 푸는 방법이 더 효율적일 것 같다.
SIDE 부분을 Queue에 넣어준 뒤, 그것들의 인접정보를 이용해서 점점 줄여나가는.. BFS 문제.
#include <iostream>
#include <cstring>
using namespace std;
int N, M;
int ARR[100][100];
bool VISIT[100][100];
int SIDE = 2;
int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, -1, 1};
int FLIP_COUNT;
int BACKUP;
void dfs(int x, int y) {
int xx, yy;
VISIT[x][y] = true;
if(ARR[x][y] == 1) {
ARR[x][y] = SIDE;
FLIP_COUNT++;
return;
}
for(int i = 0; i < 4; i++) {
xx = x + mx[i];
yy = y + my[i];
if(xx < 0 || xx >= N || yy < 0 || yy >= M)
continue;
if(!VISIT[xx][yy])
dfs(xx, yy);
}
}
int main() {
cin >> N >> M;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
cin >> ARR[i][j];
}
}
do {
BACKUP = FLIP_COUNT;
FLIP_COUNT = 0;
dfs(0, 0);
SIDE++;
memset(VISIT, 0, sizeof(VISIT));
} while(FLIP_COUNT > 0);
cout << SIDE - 3 << "\n" << BACKUP << "\n";
}
반응형
'[백준]' 카테고리의 다른 글
[BaekJoon/백준] 15685번 드래곤 커브 (0) | 2022.06.25 |
---|---|
[BaekJoon/백준] 14502번 연구소 (0) | 2022.06.24 |
[BaekJoon/백준] 2583번 영역 구하기 (0) | 2022.06.24 |
[BaekJoon/백준] 11048번 이동하기 (0) | 2022.06.23 |
[BaekJoon/백준] 11403번 경로 찾기 (0) | 2022.06.23 |