백준 10711 - 모래성(C++)

문제 링크입니다! https://www.acmicpc.net/problem/10711

10711번: 모래성

BFS를 이용한 문제였습니다.

문제 조건

출력 예시

완전 탐색을 통해서 파도 -> 모래 확인 -> 이전 모래 확인을 반복한다면, 시간 초과가 나는 문제였습니다.

(최악의 경우로서 1000*1000 배열에서 100번만 확인해도 1초가 넘습니다.)

-> BFS를 통해서 '.'의 좌표에서 8방향으로 탐색한 뒤, 모래가 전부 사라지는 곳을 다시 BFS에 넣어주는 식으로 진행해야합니다.

 

문제 접근 방법

1. '.'의 좌표를 queue에 넣어줍니다.

2. '.'의 좌표에서 8방향을 탐색한 뒤, 모래가 있으면 해당 모래에 -1를 해줍니다.

3. 모래 칸의 값이 0이 된다면, 주변 모래에 영향을 미칠 수 있음으로 queue에 넣어줍니다.

4. 해당 과정을 queue가 빌때까지 반복합니다.

 

간단한 문제임으로 위의 설명만으로도 이해가 되실겁니다!

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int N, M;
char sand[1001][1001];
int map[1001][1001];
int before[1001][1001];
int dx[8] = { 0,1,0,-1,1,1,-1,-1 };
int dy[8] = { 1,0,-1,0,1,-1,-1,1 };
queue<pair<int, int>> q;

int bfs() {
	int wave = 0;
	while (!q.empty()) {
		int q_size = q.size();
		for (int k = 0; k < q_size; k++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int i = 0; i < 8; i++) {
				int xx = x + dx[i];
				int yy = y + dy[i];
				if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
					if (map[xx][yy] > 0) {
						map[xx][yy] -= 1;
						if (map[xx][yy] == 0) q.push(make_pair(xx,yy));
					}
				}
			}
		}
		wave++;
	}
	return wave;
}

void solve() {
	cout << bfs() - 1;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> sand[i][j];
			if (sand[i][j] == '.') {
				map[i][j] = 0;
				q.push(make_pair(i, j));
			}
			else map[i][j] = sand[i][j] - '0';
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!