10711번 모래성
문제
명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다.
해변가에서 수영복을 입은 미녀들에게 관심이 많은 원철이와는 달리 명우는 해변가의 모래에 더 관심이 많다. 해변가의 모래는 무한한 것들을 만들 수 있는 가능성을 내포하고 있다. 또한 이렇게 만들어진 작품이 파도에 의해 사라지는 모습은, 마치 자신이 가장 빛날 수 있는 시간을 알고 스스로 아름답게 산화하려는 것으로 보인다. 이런 완벽에 가까운 물품인 모래를 두고서 해수욕이나 헤엄을 치는 것은 인생을 낭비하는 것과 같다고 생각한다. 하지만 아무도 명우의 말에 공감해주지 못했고, 결국 명우는 혼자서 모래성을 만들었다.
다른 친구들이 혼신의 힘을 다해 놀고있을 때 명우는 혼신의 힘을 다해 모래성을 쌓았다. 이 모래성은 언젠간 파도에 의해서 무너질 터... 명우는 이런 무너짐도 예술의 일환으로 이해한 사람이므로 무너지는 것도 고려해서 모래성을 만들었다.
그가 만든 모래성을 2차원 격자단위로 만들었으며, 각 격자마다 튼튼함의 정도를 다르게 해서 성을 만들었다. 이 튼튼함은 1부터 9 사이의 숫자로 표현될 수 있다. 이 튼튼함은, 자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다. 그 이외의 경우는 파도가 쳐도 무너지지 않는다. 모래성이 무너진 경우, 그 격자는 모래성이 쌓여있지 않은 것으로 취급한다.
이 모래성은 언젠가는 파도에 의해서 깎이고 깎여서, 결국 한가지 형태로 수렴할 것이다. 모래성을 완성한 명우는 문득 자신이 만든 예술품의 수명이 궁금해졌다. 모래성은 위에 서술한 바와 같이 파도가 한번 칠 때마다 특정 부분이 무너저내리는 방식으로 모양이 변화된다. 모래성이 더이상 모양이 변하지 않게 되려면 (모양이 수렴되려면) 파도가 몇번 쳐야하는지 구해보자.
입력
첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000)
그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다.
각 문자는 1~9 사이의 숫자, 또는 '.' 이다. 1~9는 그 격자의 모래의 강도를 나타내며, '.'는 모래가 없다는 뜻이다.
모래성은 격자의 가장자리와 접해 있지 않다.
출력
몇번의 파도가 몰려오고나서야 모래성의 상태가 수렴하는지를 구한다.
예제 입력
5 6
......
.939..
.3428.
.9393.
......
10 10
..........
.99999999.
.9.323239.
.91444449.
.91444449.
.91444449.
.91444449.
.91232329.
.99999999.
..........
예제 출력
3
35
해결방법
⭐️ 1차 시도 ⭐️
시간 초과
문제를 처음 보고 시간 복잡도를 생각해봤다
단순하게 구현하면 1000*1000 크기의 맵을 1000번 확인하는 구현이 있었다
이는 O(1000^3) 이므로 시간 초과가 발생한다
- 바다인 노드를 돌며 주변 모래성에 영향을 준다
- 만약 모래성이면서 자신의 강도(adjacent) 보다 주변의 바다가 많다면 broken 벡터에 넣는다
- broken 벡터를 돌며 모래성을 부수고 sea 벡터에 추가시켜준다
이는 시간 초과가 발생했다... 흑흑ㅠㅠ 밑에는 처음 구현한 코드이다
[소스 코드]
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 1001
#define INF 987654321
using namespace std;
typedef pair<int, int> node;
int n,m,ans;
bool flag;
char map[MAX][MAX];
bool visited[MAX][MAX];
int adjacent[MAX][MAX];
int dx[8] = {0,0,1,-1,-1,-1,1,1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
vector<node> sea;
vector<node> broken;
void getLandAdjacentSea(){
for(int i=0; i<sea.size(); i++){
int x = sea[i].first;
int y = sea[i].second;
for(int j=0; j<8; j++){
int nx = x + dx[j];
int ny = y + dy[j];
if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
if(map[nx][ny] != '.'){
adjacent[nx][ny] += 1;
}
}
}
}
void waveInSandcastle(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(map[i][j] !='.' && map[i][j]-'0' <= adjacent[i][j]){
broken.push_back(node(i,j));
flag = true;
}
}
}
}
void affectToAround(){
for(int i=0; i<broken.size(); i++){
int x = broken[i].first;
int y = broken[i].second;
for(int j=0; j<8; j++){
int nx = x + dx[j];
int ny = y + dy[j];
if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
if(map[nx][ny] != '.'){
adjacent[nx][ny] += 1;
}
}
map[x][y] = '.';
adjacent[x][y] = 0;
sea.push_back(node(x,y));
}
broken.clear();
}
int main(int argc, const char * argv[]) {
// cin,cout 속도향상
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> map[i][j];
if(map[i][j] == '.') sea.push_back(node(i,j));
}
}
memset(visited, false, sizeof(visited));
ans = 0;
getLandAdjacentSea();
while(true){
flag = false;
waveInSandcastle();
affectToAround();
if(flag) ans++;
else break;
}
cout << ans << "\n";
return 0;
}
⭐️ 2차 시도 ⭐️
맞았습니다
도저히 시간을 줄이는 방법이 생각나지않아 문제의 정답 코드를 참고했다
[ 참고 : https://www.ioi-jp.org/joi/2014/2015-yo/ ]
해결책은 큐를 사용하여 BFS 를 수행하는 것이었다
- 먼저 맵을 돌며 자신의 강도보다 인접한 바다의 수가 같거나 큰 노드를
q에 저장한다 - q 에 대해 bfs 를 수행하며 모래성을 부순다
- 부숴진 노드를 기준으로 주위 8방향의 모래성에 영향을 끼친다 (부숴진 부분은 바다가 되기 때문에)
- 만약 영향을 받은 노드 중에 부숴지는 조건에 부합된다면 해당 노드를
nq에 저장한다 - q 가 비었다면 (부숴질 예정인 모래를 다 부쉈다면) q 와 nq 를 swap 한 뒤,
ans++을 수행한다
전에 알고스팟 문제도 단계적 BFS 로 해결을 하는 코드를 짜본적이 있는데 아직 아 이 문제는 단계적 BFS 구나!! 라고 생각이 들지 않는다 ㅠㅠ 이러한 유형의 문제를 더풀어보며 연습해야겠다 흑흑
소스코드
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 1001
#define INF 987654321
using namespace std;
typedef pair<int, int> node;
int n,m;
int ans;
char map[MAX][MAX];
int adjacent[MAX][MAX];
int visited[MAX][MAX];
int dx[8] = {0,0,1,-1,1,1,-1,-1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
queue<node> q,nq;
void getAdjacentSea(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
// 모래성인 부분에서
if(map[i][j] != '.'){
// 8방향 탐색을 수행함
for(int k=0; k<8; k++){
int nx = i + dx[k];
int ny = j + dy[k];
if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
if(map[nx][ny] == '.') adjacent[i][j]++;
}
// 만약 '모래의 강도'보다 '인접한 바다의 수'가 많거나 같다면
if(map[i][j]-'0' <= adjacent[i][j]){
q.push(node(i,j));
visited[i][j] = 0;
}
}
}
}
}
void bfs(){
// q : 부서질 모래성을 저장하는 큐
// nq : 모래성이 부서지면서 인접한 노드를 검사해 부서질 예정인 부분을 저장하는 큐
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
// 모래성이 부서짐
map[x][y] = '.';
adjacent[x][y] = 0;
for(int i=0; i<8; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
if(map[nx][ny] != '.' && visited[nx][ny]==1){
adjacent[nx][ny]++;
if(map[nx][ny]-'0' <= adjacent[nx][ny]){
nq.push(node(nx,ny));
visited[nx][ny] = 0;
}
}
}
// 부서질 모래성이 모두 부숴졌다면
// 다음 부숴질 예정인 모래성이 담겨있는 nq 와 교환
// 다 부수고 나서 ans+1 을 수행함
if(q.empty()){
swap(q, nq);
ans++;
}
}
}
int main(int argc, const char * argv[]) {
// cin,cout 속도향상
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> map[i][j];
if(map[i][j] != '.')
visited[i][j] = 1;
}
}
ans = 0;
getAdjacentSea();
bfs();
cout << ans << "\n";
return 0;
}
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 1001
using namespace std;
struct node {
int x,y;
node() { }
node(int _x,int _y) : x(_x),y(_y) { }
};
int n,m,ans=0;
char in;
int map[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX];
int dx[8] = {0,0,-1,1,-1,-1,1,1};
int dy[8] = {1,-1,0,0,-1,1,-1,1};
queue<node> q,nq;
void printMap(){
cout << "\n";
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cout << map[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
}
void bfs(){
while(!q.empty()){
int x = q.front().x;
int y = q.front().y;
q.pop();
for(int i=0; i<8; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 맵 밖을 나가거나 이미 방문한 경우
if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
if(visited[nx][ny]) continue;
// 모래성
if(map[nx][ny] != 0){
dist[nx][ny] += 1;
// 모래성이 무너진다면
if(dist[nx][ny] >= map[nx][ny]){
nq.push(node(nx,ny));
visited[nx][ny] = true;
}
}
}
if(q.empty()){
if(!nq.empty()) ans++;
while(!nq.empty()){
int nx = nq.front().x;
int ny = nq.front().y;
nq.pop();
map[nx][ny] = 0;
q.push(node(nx,ny));
}
}
// printMap();
}
cout << ans << "\n";
}
int main(int argc, const char * argv[]) {
// cin,cout 속도향상
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// 초기화
memset(visited, false, sizeof(visited));
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> in;
if(in == '.'){
map[i][j] = 0;
q.push(node(i,j));
visited[i][j] = true;
}else{
map[i][j] = in -'0';
}
}
}
bfs();
return 0;
}
'Algorithm > BOJ 문제풀이' 카테고리의 다른 글
| [BF] 3085번 사탕 게임 (0) | 2019.01.04 |
|---|---|
| [BF] 2331번 분해합 (0) | 2019.01.04 |
| [BFS] 14395번 4연산 (0) | 2019.01.04 |
| [BFS] 12906번 새로운 하노이 탑 (1) | 2019.01.04 |
| [BFS] 12886번 돌 그룹 (0) | 2019.01.04 |
