[C++] 백준 2573번 빙산

2573번: 빙산

구현 / 그래프 탐색 문제.

삼성 기출 문제와 유사한 문제였다.

문제에서 제시하는대로 구현하면 맞출 수 있는 문제다.

 

문제풀이

다음과 같은 순서로 만들면 된다.

1. 0이 아닌 칸들에서 인접한 칸들 중 0인 칸들의 개수를 큐에 저장해둔다.
2. 큐에 있는 정보를 토대로 각 칸마다 0인 칸들의 개수만큼 높이에서 빼준다.
3. DFS / BFS를 통해 연결 요소의 개수를 구해서 2 이상인 경우에는 몇 년 걸렸는지 출력한다.
4. 2 미만일 경우에는 1로 돌아간다. 이 때 DFS / BFS를 위해 방문 처리를 해제시켜놓는다.

이 때 입력받은 최초의 순간에도 연결 요소의 개수가 2개 이상일 수 있으므로

입력을 받은 직후에 DFS / BFS를 해보고, 연결 요소의 개수가 2개 미만일 때만 위와 같은 로직을 시작한다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int height, width;
int iceAge[301][301];
bool visit[301][301];
int ans;
vector<pair<int, int>> icePoint;
queue<pair<int, pair<int, int>>> q;
pair<int, int> direction[4] = {
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1}
};

사용한 STL과 변수

• height, width : 입력받는 N과 M
• iceAge 배열 : 각 칸에서 빙산의 높이를 나타내는 배열
• visit 배열 : DFS / BFS를 할 때 (r, c)를 방문했는지 여부를 저장하는 배열
• ans : 출력하는 결과값.
• icePoint 벡터 : 현재 얼음이 남아있는 곳의 좌표
• q 큐 : 높이가 1 이상인 빙산에서, 주변 칸이 0인 것의 개수만큼 빼주기 위해 기록해두는 큐. { 0인 칸의 개수, {r, c} }의 형태이다.
• direction 배열 : 상, 하, 좌, 우를 탐색하기 위해 만든 배열.

 

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> height >> width;

	for (int i = 1; i <= height; i++) {
		for (int j = 1; j <= width; j++) {
			cin >> iceAge[i][j];
			if (iceAge[i][j] > 0) { icePoint.push_back({ i, j }); }
		}
	}

	if (!checkSeparate()) {
		ans = go(1);
	}

	if (ans != -1) {
		cout << ans;
	}
	else {
		cout << 0;
	}

	return 0;
}

메인함수.

처음에 N, M을 입력받고 각 칸의 정보를 입력받는다.

만일 칸이 0보다 큰 경우, icePoint벡터에 해당 좌표를 입력시켜 놓는다.

 

그리고 위에서 설명했듯이 입력받은 직후에도 분리가 돼 있는 상태일 수 있으므로

DFS / BFS를 해서 연결 요소의 개수를 찾는다.

checkSeparate() 메서드는 방문하지 않은 좌표부터 시작해서 DFS / BFS를 진행한 후에

연결 요소의 개수가 2개 이상이라면 true, 미만이라면 false를 return하는 메서드이다.

따라서 해당 메서드가 false를 return한 경우에만 즉, 입력받은 직후에는 분리되지 않은 경우에만

위에서 설명한 로직을 실행시킨다. 로직을 구현한 메서드는 go() 메서드이다.

 

로직이 끝나게 되면 ans가 -1 또는 다른 값이 될텐데, -1은 얼음이 다 녹을 때 까지 분리가 되지 않은 경우이다.

이때는 0을 출력하고 나머지 경우는 그냥 ans를 출력한다.

 

bool checkSeparate() {
	int connectedComponents = 0;

	for (int i = 0; i < icePoint.size(); i++) {
		int r = icePoint[i].first;
		int c = icePoint[i].second;
		if (!visit[r][c] && iceAge[r][c] > 0) {
			connectedComponents++;
			dfs(r, c);
		}
	}
	return (connectedComponents >= 2);
}

void dfs(int r, int c) {
	visit[r][c] = true;

	for (pair<int, int> dir : direction) {
		int adjR = r + dir.first;
		int adjC = c + dir.second;

		if (adjR <= 0 || adjR > height || adjC <= 0 || adjC > width || 
			iceAge[adjR][adjC] == 0 || visit[adjR][adjC]) { continue; }

		dfs(adjR, adjC);
	}
}

연결요소의 개수를 찾는 메서드와 dfs 메서드.

모든 점을 고려할 필요없이, icePoint에 저장된 좌표들만 고려해주면 된다.

방문하지 않은 점이 있다면, connectedComponents에 1을 더해준 후에 해당 점을 기점으로 dfs를 진행한다.

그리고 connectedComponents >= 2 가 true인지를 return한다.

 

dfs의 경우에는 유효한 범위인지, 해당 칸이 0이 아닌지, 방문한 곳은 아닌지 확인한 후에 다음 칸으로 가는 식으로 만들었다.

 

int go(int curYear) {
	findZeroCnt();

	if (q.size() == 0) { return -1; }

	minusAdjZeroCnt();

	if (checkSeparate()) {
		return curYear;
	}
	else {
		return go(curYear + 1);
	}
}

위에서 설명한 로직.

findZeroCnt() 메서드로 빙산들의 인접한 칸들 중 0인 것들의 개수를 찾아서 큐에 넣어놓는다.

만일 큐의 사이즈가 0이라는 뜻은, 더이상 높이를 빼줄 빙산이 없다는 것을 의미한다. 이런 경우 -1을 return한다.

 

minusAdjZeroCnt() 메서드로는 큐에 저장된 정보들을 토대로 해당 칸들에 인접한 0인 것들의 개수만큼 높이에서 빼준다.

 

그러고나서 checkSeparate() 메서드로 연결 요소 개수가 2개 이상이라면 현재 년도를 return하고, 아니라면 1년 더 진행한다.

 

void findZeroCnt() {
	for (int i = 0; i < icePoint.size(); i++) {
		int r = icePoint[i].first;
		int c = icePoint[i].second;

		visit[r][c] = false; // 겸사겸사초기화

		if (iceAge[r][c] == 0) {
			icePoint.erase(icePoint.begin() + i);
			i--;
			continue;
		}

		int adjZero = 0;
		for (pair<int, int> dir : direction) {
			int adjR = r + dir.first;
			int adjC = c + dir.second;

			if (adjR <= 0 || adjR > height || adjC <= 0 || adjC > width) { continue; }

			if (iceAge[adjR][adjC] == 0) { adjZero++; }
		}

		q.push({ adjZero, {r, c} });
	}
}

빙산들 중 주변의 0인 칸들의 개수를 찾는 메서드.

 

icePoint 벡터에서만 고려해주면 된다.

 

그리고 이 메서드를 진행할 때, DFS를 진행시키기 위해 방문여부도 초기화하는 로직을 같이 구현해놨다.

(가독성 부분에 있어서 좋은 방법은 아니긴 하지만, 알고리즘은 속도가 중요하다 보니 같이 써놓긴 했다. 물론 큰 차이는 없다.)

만일 현재 탐사하려는 칸의 높이가 0이라면, icePoint 벡터에서 해당 칸의 정보를 벡터 STL에 있는 erase() 메서드로 삭제한다. 삭제를 하면 icePoint 벡터의 사이즈도 1 줄어드므로 i를 다시 한 번 1 빼줘서 다음 idx를 정상적으로 탐사하도록 한다.

 

높이가 0이 아닌 경우에는 상, 하, 좌, 우를 탐색해서 높이가 0인 것들의 개수를 찾아서 좌표와 함께 큐에 넣어준다.

 

void minusAdjZeroCnt() {
	while (!q.empty()) {
		int minusNum = q.front().first;
		int r = q.front().second.first;
		int c = q.front().second.second;
		q.pop();
		iceAge[r][c] -= minusNum;
		if (iceAge[r][c] < 0) { iceAge[r][c] = 0; }
	}
}

인접한 0인 칸들의 개수를 빼주는 메서드.

큐에 담긴 것들을 모두 처리한다.

만일 높이가 음수가 됐다면 0으로 만들어준다.

 

처음에 go()메서드에서 return을 빼먹어서 틀렸었다.

(백준은 참 친절하다...)

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인 가능하다.