BOJ 10711

30 Jan 2020 • ProblemSolving

모래성

문제출처

1.설계(20)

  • 문제 해석

    • 모래성이 변하지 않을 때까지 파도가 얼마나 쳐야 되는지 알아보는 문제입니다.
    • 2차원 배열에 튼튼함의 정도를 표현하는 숫자(1~9)가 있고, 파도는 ‘.’로 표현됩니다.
    • 숫자주위의 8방향 중에 모래성이 쌓이지 않은 부분의 개수가 숫자보다 많거나 같으면 모래성은 무너지게 됩니다.

  • 설계

    • 해당 문제는 bfs문제로 풀 수 있습니다. 숫자를 기준으로 탐색을 하는게 아닌 파도(0)을 기준으로 탐색을 하여, 모래성을 줄여나가면 됩니다.
    • 처음에 2차원 vistied 배열을 주어 모래성이 무너진 부분을 방문표시하도록 구현하였으나, 중복 탐색되는 부분이 많아서 시간초과가 났습니다.
    • 큐에 담겨있는 파도들을 옮기면서 모래성의 숫자를 1씩 줄여나가면 해당 모래성이 무너지는지 판단할 수 있습니다.

2.구현(35)

  • 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 1002
int dx[] = { -1,-1,-1,0,0,1,1,1 };
int dy[] = { -1,0,1,-1,1,-1,0,1 };

int map[MAXN][MAXN];
int copy_map[MAXN][MAXN];
int N, M;
queue<pair<int, int> > q;


int bfs() {
	
	int time = 0;
	while (!q.empty()) {
		int q_size = q.size(); 
		
		while (q_size--) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int k = 0; k < 8; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if (map[nx][ny] > 0) {
					map[nx][ny]--;
					if (map[nx][ny] == 0) {
						q.push({ nx,ny });
					}
				}
			}
		}
		
		time++;
	}
	return time-1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			char tmp;
			scanf(" %1c", &tmp);
			if (tmp == '.') {
				q.push({ i,j });
			}
			else {
				map[i][j] = tmp - '0';
			}
		}
	}
	printf("%d\n", bfs());
	return 0;
}

  • 디버깅

    • 편의성을 위해 map을 int형으로 선언하였습니다.

  • 제출결과

    72ms

3.마무리

  • 약간 응용된 bfs문제입니다. 파도를 기준으로 탐색하는 아이디어를 찾는 게 관건이었습니다.
 BOJ

Related Posts