[백준 2573] 빙산

지금까지 푼 DFS/BFS 문제 중 제일 난이도 있는 문제였음

풀면서 BFS뿐만 아니라 그 외 것들을 구현하는데 생각을 더 해야했음

 

1. 우선 가장 중요한건 BFS돌면서 빙하를 녹이면 안된다는거임

 

왜냐하면 하면서 녹이면 그 다음꺼가 바다랑 맞닿는 면의 개수에 영향을 끼치기 때문

그래서 녹일 양을 따로 저장해야함

 

2. 그 다음으로 중요한게 2분할 됐냐 확인하는거임

 

이건 모든 원소 다 돌면서 visited 됐는지 확인하고 BFS돌리고 그러면서 cnt++ 해서 판단가능함

 

BFS 한 턴으로 다 돌면 정상이고

BFS가 두 턴 이상 나오면 break

BFS가 0이면 다 녹았다는 뜻이므로 종료

 

BFS가 0번이면 그건 다 녹을때까지 cnt가 두 번 이상 안나왔다는 뜻이므로 바로 종료해주면 된다

 

	for (int i = 0; i < iceberg.size(); i++) {
		int y = iceberg[i].first;
		int x = iceberg[i].second;

		// 빙하가 있고 아직 탐색X
		if (ocean[y][x] && !visited[y][x]) {
			BFS(y, x);
			cnt++;
		}
	}

	// 다 녹았으면
	if (cnt == 0) { cout << "0"; break; }
	// 만약 이분할 되었으면 종료
	if (cnt > 1) { cout << year; break; }

 

 

3. 빙하 위치는 희소행렬로 저장해놓자 

 

4. 사분면은 dx dy로 미리 저장해놓음. 거의 dfs bfs 할때 필수

 

쨋든... 뭐 재밌는 문제인데 시간이 많이 걸림

 

참고로 vs에서는 memset이 바로 되는데 백준은 cstring이나 memory.h 안해주면 컴파일 에러뜸...

개억울하게 컴파일에러 하나 적립함...

 

---

엔샵하다 다시 코테 감 잡는다고 다시 푼 풀이

첫번째보다 훨씬 잘 푼듯

#include <iostream>
#include <vector>
#include <queue>
#include <bitset>

#define SIZE 301

using namespace std;

int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

int N, M;
int map[SIZE][SIZE];
int ans;
vector<pair<int, int>> iceberg;

// 한번의 BFS로 확인한 녹아야하는 빙하 좌표와 녹는 양
vector<pair<pair<int, int>, int>> melting;

void bfs() {
	queue<pair<int, int>> q;
	bitset<SIZE> visited[SIZE];

	q.push(make_pair(iceberg[0].first, iceberg[0].second));
	visited[iceberg[0].first][iceberg[0].second] = 1;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		int meltingcnt = 0;

		for (int i = 0; i < 4; i++) {
			int newy = y + dy[i];
			int newx = x + dx[i];

			if (map[newy][newx] == 0) meltingcnt++;

			// 빙하고 아직 방문 안했으면
			if (map[newy][newx] && !visited[newy][newx]) {
				visited[newy][newx] = 1;
				q.push(make_pair(newy, newx));
			}
		}

		melting.push_back(make_pair(make_pair(y, x), meltingcnt));
	}
}

void meltice() {
	// 녹여주기
	for (int i = 0; i < melting.size(); i++) {
		int y = melting[i].first.first;
		int x = melting[i].first.second;
		int cnt = melting[i].second;

		map[y][x] -= cnt;
		if (map[y][x] <= 0) map[y][x] = 0;
		else {
			iceberg.push_back(make_pair(y, x));
		}
	}

	melting.clear();
}

void solve() {
	
	int ans = 0;

	while(1) {

		bfs();
		
		// 빙하가 두 개로 나눠졌으면 종료
		if (melting.size() != iceberg.size()) break;

		iceberg.clear();
		
		meltice();

		if (iceberg.size() == 0) {
			cout << 0;
			return;
		}

		ans++;
	}

	cout << ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> M;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
			if (map[y][x] > 0) {
				iceberg.push_back(make_pair(y, x));
			}
		}
	}

	if (iceberg.size() == 0) {
		cout << 0;
		return 0;
	}

	solve();

	return 0;
}

 

실제로 시간이랑 메모리도 반이상 줄었다

 

이분할됐는지 확인하는것을 따른 배열로 하지 않고

그냥 melting 배열을 사용해서 확인함

iceberg랑 melting vector 크기가 같으면 아직 이분할 안됐다는거 확인가능

---

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

#define SIZE 300

using namespace std;

int N, M;
int ocean[SIZE][SIZE];
int melt[SIZE][SIZE];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

bool visited[SIZE][SIZE];

// 빙하 희소행렬
vector<pair<int, int>> iceberg;

// 빙하 BFS
void BFS(int y,int x) {

	queue<pair<int,int>> q;
	q.push(make_pair(y,x));

	while (!q.empty()) {
		
		int posy = q.front().first;
		int posx = q.front().second;
		q.pop();

		// 해당 빙하를 방문하지 않았으면
		if (!visited[posy][posx]) {
			
			// 방문처리 해주고
			visited[posy][posx] = true;

			int melting = 0;

			for (int i = 0; i < 4; i++) {
				
				int newy = posy + dy[i];
				int newx = posx + dx[i];
				
				// 범위 내
				if (newy >= 0 && newy < N && newx >= 0 && newx < M) {
					// 아직 방문 안한 빙하
					if (ocean[newy][newx] && !visited[newy][newx]) q.push(make_pair(newy, newx));
					// 바다
					if(!ocean[newy][newx]) melting++;
				}
			}

			// 추후에 녹일 빙산 저장
			melt[posy][posx] = melting;
		}
	}

	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> ocean[i][k];
			if (ocean[i][k]) {
				iceberg.push_back(make_pair(i, k));
			}
		}
	}

	int year = 0;
	int cnt;

	while(1){
		// 빙하 BFS
		cnt = 0;
		memset(visited, false, sizeof(visited));
		
		for (int i = 0; i < iceberg.size(); i++) {
			int y = iceberg[i].first;
			int x = iceberg[i].second;

			// 빙하가 있고 아직 탐색X
			if (ocean[y][x] && !visited[y][x]) {
				BFS(y,x);
				cnt++;
			}
		}

		// 빙하 녹여주기
		for (int i = 0; i < iceberg.size(); i++) {
			int y = iceberg[i].first;
			int x = iceberg[i].second;
			if (ocean[y][x]) ocean[y][x] -= melt[y][x];
			if (ocean[y][x] < 0) ocean[y][x] = 0;
		}

		// 다 녹았으면
		if (cnt == 0) { cout << "0"; break; }
		// 만약 이분할 되었으면 종료
		if (cnt > 1) { cout << year; break; }
		
		// 1이면 계속 실행
		year++;
	}
	
	return 0;
}