[G1] 백준 1113번 수영장 만들기 C++ 구현, 시뮬레이션, 너비 우선 탐색, 플러드 필

리뷰

 

https://www.acmicpc.net/problem/1113

낮은 수 부터 순회하며 플러드 필을 통해 해결하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• dx, dy : 4방향 탐색을 위한 방향 배열
• n, m : 맵의 세로/가로 길이를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 맵 정보를 저장할 2차원 배열
• v : 방문 여부를 저장할 2차원 배열
• Pos : 위치 정보를 정의할 구조체

 

함수

1. flood_fill

void flood_fill(int sx, int sy, int ch) {
	queue<Pos> q;
	q.push({ sx, sy });
	queue<Pos> memo;
	memo.push({ sx, sy });
	v[sx][sy] = true;
	int mh = 9;
	bool flag = true;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];

			if (0 > nx || nx >= n || 0 > ny || ny >= m) {
				flag = false;
				continue;
			}

			if (lst[nx][ny] < ch) {
				flag = false;
				continue;
			}

			if (v[nx][ny]) continue;

			if (lst[nx][ny] == ch) {
				v[nx][ny] = true;
				q.push({ nx, ny });
				memo.push({ nx, ny });
			}
			else if (mh > lst[nx][ny]) mh = lst[nx][ny];
		}
	}

	if (flag) {
		while (!memo.empty()) {
			Pos pos = memo.front(); memo.pop();
			int x = pos.x, y = pos.y;

			lst[x][y] = mh;
			ans += mh - ch;
			v[x][y] = false;
		}
	}
}

 

플러드 필을 사용해 물이 담길 수 있는 공간인지 여부를 체크하고, 물을 담는 시뮬레이션을 수행할 함수

 

2. print

void print() {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << lst[i][j];
		}
		cout << "\n";
	}
}

 

디버깅용 출력 함수

 

 

문제풀이

1. n, m값을 입력 받고, n*m크기의 초기 맵 정보를 입력받아 lst배열을 초기화한다.
2. 1~9를 순회하며 추가로 n*m크기의 맵을 순회한다.
3. 이미 방문 처리되어있거나, 현재 좌표가 h와 맞지 않은 높이인경우 continue처리한다.
4. flood_fill함수에 i, j, h를 매개변수로 전달하여 호출한다. 함수 내부에서 변수 sx, sy, ch에 매개변수를 전달받는다.
5. Pos타입의 큐 q, memo를 초기화 하고, 각각 sx, sy를 추가한다.
6. v[sx][sy]에 방문처리 후, 변수 mh를 9로, flag를 true로 초기화한다.
7. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 변수 cx, cy에 파싱한다.
8. 4방향 탐색을 진행하고, 이동할 위치를 nx, ny로 저장한다.
9. nx, ny가 맵 경계선 밖일 경우 flag를 false로 변경 후 continue처리한다.
10. lst[nx][ny]가 ch보다 작을 경우 flag를 false로 변경 후 continue처리한다.
11. v[nx][ny]가 방문한 지역이라면 continue처리한다.
12. lst[nx][ny]가 ch와 같다면 v[nx][ny]에 방문처리 후 q, memo에 각각 nx, ny를 추가한다.
13. lst[nx][ny]가 mh보다 작다면 mh를 lst[nx][ny]값으로 저장한다.
14. while루프가 종료된 후 flag가 true인 경우 memo가 빌때까지 while루프를 수행한다. 모든 요소의 좌표를 순회하며 맵 상에서 값을 mh로 변경하고, mh-ch를 ans에 더해주고 v배열에서 방문 처리를 해제한다.
15. 모든 높이별 수영장을 순회하며 최종적으로 ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다.
2. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.
3. 1~9높이를 순차 순회하며 플러드필 함수를 통해 아래 내용을 순차적으로 처리하면 된다.
4. 맵의 밖과 연결된 그룹은 벽으로만 사용할 수 있으므로 모두 다시 방문하지 않게한다.
5. 더 큰수들로 둘러쌓인 그룹은 둘러싼 값 중 가장 작은 값을 기준으로 물을 채운다.
6. 이때 물을 채운 후 방문처리를 제거하여 다음 물 높이 탐색 시 해당 지역을 다시 탐색하도록한다.
7. 사실상 9는 벽으로만 사용 가능하므로 탐색을 해줄 필요가 없어보인다.
8. 맵 정보를 입력 받을때 최대 물 높이를 저장하고, 해당 물 높이까지만 탐색해도 가지치기가 될 것 같다.
9. 가지치기를 별도 수행하지 않아도 수행시간이 0ms가 나와서 별도의 가지치기는 생략했다.
10. 입력값이 공백 등으로 분리되어 있지 않기 때문에 문자로 입력 받아 정수로 파싱하는걸 추천한다.

 

정답 코드

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

const int N = 50;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n, m, ans;
int lst[N][N];
bool v[N][N];
struct Pos {
	int x, y;
};

void flood_fill(int sx, int sy, int ch) {
	queue<Pos> q;
	q.push({ sx, sy });
	queue<Pos> memo;
	memo.push({ sx, sy });
	v[sx][sy] = true;
	int mh = 9;
	bool flag = true;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];

			if (0 > nx || nx >= n || 0 > ny || ny >= m) {
				flag = false;
				continue;
			}

			if (lst[nx][ny] < ch) {
				flag = false;
				continue;
			}

			if (v[nx][ny]) continue;

			if (lst[nx][ny] == ch) {
				v[nx][ny] = true;
				q.push({ nx, ny });
				memo.push({ nx, ny });
			}
			else if (mh > lst[nx][ny]) mh = lst[nx][ny];
		}
	}

	if (flag) {
		while (!memo.empty()) {
			Pos pos = memo.front(); memo.pop();
			int x = pos.x, y = pos.y;

			lst[x][y] = mh;
			ans += mh - ch;
			v[x][y] = false;
		}
	}
}

void print() {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << lst[i][j];
		}
		cout << "\n";
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char c; cin >> c;
			lst[i][j] = c - '0';
		}
	}

	for (int h = 1; h <= 9; ++h) {
		//cout << "\n";
		//print();
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (v[i][j]) continue;
				if (lst[i][j] != h) continue;
				flood_fill(i, j, h);
			}
		}
	}
	cout << ans;
}