BOJ - 2573번 빙산(C++)

문제 출처: https://www.acmicpc.net/problem/2573

문제 난이도

Gold 4

문제 접근법

그래프 탐색 이용해서 하는 구현 문제라 어려운 것은 없다.
단지, 신경쓸 게 덩어리를 어떻게 구분해서 counting 하는 것을 신경써서 풀었다.

처음엔, queue를 2개 써서 count 했지만 틀렸습니다 가 뜬 후로 매번 bfs로 탐색하는 걸로 바꿨다.

통과 코드

#include <iostream>
#include <algorithm>
#include <queue>


using namespace std;

int N, M;
bool ch[301][301];
int arr[301][301];
int board[301][301];
int dy[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };//위,아래,왼,오

void iceCheck(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x,y });
	ch[x][y] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dy[i][0];
			int ny = y + dy[i][1];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M || ch[nx][ny] || arr[nx][ny] == 0) continue;
			q.push({ nx,ny });
			ch[nx][ny] = true;
		}
	}
}

int zeroCnt(int x, int y) {
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dy[i][0];
		int ny = y + dy[i][1];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		if (arr[nx][ny] == 0) cnt++;
	}
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	queue<pair<int, int>> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}

	int year = 0;

	while (1) {
		memset(board, 0, sizeof(board));
		memset(ch, false, sizeof(ch));
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] != 0 && !ch[i][j]) {
					iceCheck(i, j);
					cnt++;
				}
				if (arr[i][j] > 0) q.push({ i,j });
			}
		}
		if (cnt >= 2) break;
        	else if(cnt ==0){
            		year = 0;
            		break;
        	}
		while (!q.empty()) {
			int x = q.front().first;
			int y = q.front().second;
			int zCnt = zeroCnt(x, y);
			board[x][y] = arr[x][y] - zCnt;
            		if(board[x][y] < 0) board[x][y] = 0;
			q.pop();
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = board[i][j];
			}
		}
		year++;
		
	}

	cout << year << "\n";

	return 0;
}

피드백

시도 1.
처음 구현한 iceCheck 코드

int iceCheck(queue<pair<int, int>> q) {
	queue<pair<int, int>> q2;
	memset(ch, false, sizeof(ch));
	int cnt = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (ch[x][y]) continue;
		if (q2.empty()) q2.push({ x,y });
		while (!q2.empty()) {
			int qX = q2.front().first;
			int qY = q2.front().second;
			q2.pop();
			for (int i = 0; i < 4; i++) {
				int nx = qX + dy[i][0];
				int ny = qY + dy[i][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M || ch[nx][ny] || arr[nx][ny] == 0) continue;
				q2.push({ nx,ny });
				ch[nx][ny] = true;
			}
		}
		cnt++;
	}
	return cnt;
}

시도 2.

board[x][y] = arr[x][y] - zCnt;
if(board[x][y] < 0) board[x][y] = 0;

board[x][y]가 음수 나올 경우를 체크 안해서 틀렸다.
zeroCnt를 세는 게 if(arr[i][j] == 0)일 때 세는 거기때문에 오류가 있었다. 만약 음수임을 신경안쓰고 싶으면 zeroCnt 할때 if(arr[i][j] < 0)로 하면 통과한다.

시도 3.
그리고 다 구현하고 돌리니깐 시간초과가 났다.

else if(cnt == 0){
	year = 0;
	break;
}

를 추가하니깐 통과했다. 처음엔 cnt=0이라는 건 빙산이 없다는 것이니깐 몇년이 지난 후 빙산이 녹았다니깐 당연히 year 그대로 출력해야한다고 생각했다. 그래서 0이라고 대입안하고 통과하니깐 틀렸습니다가 떴고, 다시 문제를 읽어보니
만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 를 봤다!
문제를 좀 꼼꼼히 읽자!!