[G2] 백준 10711번 모래성 C++ 너비 우선 탐색

리뷰

 

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

골드 2문제 치고는 좀 쉬운 문제였던 것 같다. 차라리 치즈 문제 시리즈가 더 까다로웠던 것 같은듯?

치즈 시리즈 문제 추천이다.

[G4] 백준 2636번 치즈 C++ 너비 우선 탐색, 플러드 필, BFS, Flood Fill

[G4] 백준 2636번 치즈 C++ 너비 우선 탐색, 플러드 필, BFS, Flood Fill

[G3] 백준 2638번 치즈 C++ 너비 우선 탐색, 해시맵, 구현, 시뮬레이션

[G3] 백준 2638번 치즈 C++ 너비 우선 탐색, 해시맵, 구현, 시뮬레이션

 

 

전역 변수

• n, m : 맵의 세로/가로 길이를 저장할 변수
• lst : 맵 정보를 저장할 변수
• dx, dy : 8방향 탐색을 위한 방향 배열
• Pos : 좌표 정보x, y를 정의하기 위한 구조체
• q1 : 모래가 없는 곳의 좌표를 담기 위한 Pos타입의 큐

 

함수

1. solution

int solution()

 

모래성의 변화가 없기 까지의 최대 시간을 구하기 위한 함수

1. 함수의 결과를 리턴할 변수 result의 초기값을 0으로 초기화를 진행해 준다.
2. q1이 빌 때 까지 while루프를 수행하고, 매 루프마다 Pos타입의 큐 p2를 초기화 한 뒤, q1과 q2를 swap해준다.
3. q2가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
4. 각 요소의 위치에서 8방향 탐색 후, 맵의 범위에 있으며 이동 위치의 lst에 저장된 의 값이 0이 아닐 경우 이동한다.
5. 이동한 지역의 값을 1만큼 줄여준 뒤 만약 0이 된 경우 q1에 해당 위치 정보를 push해준다.
6. 만약 q1가 빈 상태가 아니라면 result를 증가시켜 준다.
7. 모든 루프가 종료된 경우 result에 저장된 값을 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받고, n * m크기의 맵 정보를 입력 받아준다.
2. 이 때, '.'일 경우 0으로 저장 및 q1에 push해 주었다.
3. 만약 '.'이 아닐 경우 정수 그 자체를 맵에 저장해 주었다.
4. solution함수를 호출하고 전달 받은 리턴값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 이런 식으로 구현을 하면 별도의 방문처리 없이 매 위치를 1번만 조회하여 시뮬레이션을 돌릴 수 있다.
• 큐 두개를 사용하고 매번 swap을 해주었는데, 큐를 한개만 사용해 구현했더니 4배가 빨라졌다.

 

정답 코드

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

int n, m;
int lst[1000][1000];
int dx[] = { 1, 1, 1, 0, 0, -1, -1, -1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
struct Pos {
	int x, y;
};
queue<Pos> q;

int solution() {
	int result = 0;
	while (!q.empty()) {
		int len = q.size();
		while (len--) {
			Pos pos = q.front(); q.pop();
			int cx = pos.x, cy = pos.y;

			for (int i = 0; i < 8; ++i) {
				int nx = cx + dx[i], ny = cy + dy[i];
				if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny]) {
					if (--lst[nx][ny] == 0) q.push({ nx, ny });
				}
			}
		}
		if (!q.empty()) result++;
	}
	return result;
}

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 ch; cin >> ch;
			if (ch == '.') {
				lst[i][j] = 0;
				q.push({ i, j });
			}
			else lst[i][j] = ch - '0';
		}
	}
	cout << solution();
}