[백준_10711번] 모래성

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

10711번: 모래성

[문제]

 명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다. 해변가에서 수영복을 입은 미녀들에게 관심이 많은 원철이와는 달리 명우는 해변가의 모래에 더 관심이 많다. 해변가의 모래는 무한한 것들을 만들 수 있는 가능성을 내포하고 있다. 또한 이렇게 만들어진 작품이 파도에 의해 사라지는 모습은, 마치 자신이 가장 빛날 수 있는 시간을 알고 스스로 아름답게 산화하려는 것으로 보인다. 이런 완벽에 가까운 물품인 모래를 두고서 해수욕이나 헤엄을 치는 것은 인생을 낭비하는 것과 같다고 생각한다. 하지만 아무도 명우의 말에 공감해주지 못했고, 결국 명우는 혼자서 모래성을 만들었다.

 다른 친구들이 혼신의 힘을 다해 놀고있을 때 명우는 혼신의 힘을 다해 모래성을 쌓았다. 이 모래성은 언젠간 파도에 의해서 무너질 터... 명우는 이런 무너짐도 예술의 일환으로 이해한 사람이므로 무너지는 것도 고려해서 모래성을 만들었다.

 

 그가 만든 모래성을 2차원 격자단위로 만들었으며, 각 격자마다 튼튼함의 정도를 다르게 해서 성을 만들었다. 이 튼튼함은 1부터 9 사이의 숫자로 표현될 수 있다. 이 튼튼함은, 자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다. 그 이외의 경우는 파도가 쳐도 무너지지 않는다. 모래성이 무너진 경우, 그 격자는 모래성이 쌓여있지 않은 것으로 취급한다.

 이 모래성은 언젠가는 파도에 의해서 깎이고 깎여서, 결국 한가지 형태로 수렴할 것이다. 모래성을 완성한 명우는 문득 자신이 만든 예술품의 수명이 궁금해졌다. 모래성은 위에 서술한 바와 같이 파도가 한번 칠 때마다 특정 부분이 무너저내리는 방식으로 모양이 변화된다. 모래성이 더이상 모양이 변하지 않게 되려면 (모양이 수렴되려면) 파도가 몇번 쳐야하는지 구해보자.

 

[입력 조건]

• 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000)
• 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다.
• 각 문자는 1~9 사이의 숫자, 또는 '.' 이다. 1~9는 그 격자의 모래의 강도를 나타내며, '.'는 모래가 없다는 뜻이다.
• 모래성은 격자의 가장자리와 접해 있지 않다.

 

[코드]

import java.util.*;

class Point_10711 {
	int x, y;
	
	public Point_10711(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_10711 {
	static char[][] map;
	static int n,m;
	static int[] dx= {0,0,1,1,1,-1,-1,-1}; // 상,하,우,좌,대각선
	static int[] dy= {-1,1,-1,0,1,-1,0,1};
	static Queue<Point_10711> nosand=new LinkedList<>(); // 모래가 없는 곳의 좌표 저장
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new char[n][m];
		
		for(int i=0;i<n;i++) {
			String str=sc.next();
			for(int j=0;j<m;j++) {
				map[i][j]=str.charAt(j);
				
				// 모래가 없는 곳 큐에 삽입
				if(map[i][j]=='.') 
					nosand.add(new Point_10711(i,j));
			}
		}
		System.out.println(wave());
	}
	
	/*
	 * 시간초과를 받지 않기 위해 모래성의 주위를 탐색하는 것이 아닌
	 * 모래가 없는 칸을 기준으로 8방향에 모래성의 튼튼함을 1 감소시킨다.
	 * 이때 이미 하번 확인한 모래성이 없는 노드는 다시 확인할 필요가 없기 때문에
	 * 새로 모래성이 없어진 곳만 큐에 삽입해준다.
	 */
	static int wave() {
		int time=0;
		
		// 큐에 값이 없으면 더 이상 변화가 없는 상태 -> 종료
		while(!nosand.isEmpty()) {
			int size=nosand.size();
			
			// 한 턴에 큐에 쌓인 값들만 처리하고 시간 증가 -> 모래성은 한 번에 무너져야 하기 때문에
			while(size-->0) {
				Point_10711 p=nosand.poll();
				
				int x=p.x;
				int y=p.y;
				
				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) {
						if(map[nx][ny]!='.') {
							map[nx][ny]--; // 모래성의 튼튼함 1 감소시킨다.
							
							// 튼튼함이 0이되면 모래가 없는 칸으로 변경하고 큐에 삽입
							if(map[nx][ny]=='0') {
								map[nx][ny]='.';
								nosand.add(new Point_10711(nx,ny));
							}
						}
					}
				}
			}
			time++; // 초 증가
		}
		
		return time-1;
	}
}

 

[고찰]

 처음에 해당 문제를 접근할때는 모래성이 있는 칸을 기준으로 8방향을 탐색해 모래성이 없는 칸을 count 하는 방법을 사용했었다. 하지만 이렇게 풀면 시간초과를 받기 때문에 새로운 관점이 필요했다. 스스로 떠올리기에는 한계를 느껴 다른 사람의 코드를 참고하여 해결하였다. 

 이번 문제의 핵심은 모래성이 있는 칸을 기준으로 두는것이 아닌 모래성이 없는 칸을 기준으로 삼는 것이었다. 백준 2636번 치즈 문제를 풀 때도 치즈가 있는 칸이 아닌 공기가 있는 칸의 좌표를 큐에 저장했었는데 같은 풀이 방법이었다. 우선 맵의 정보를 입력받을 때 초기의 모래성이 없는 좌표를 큐에 저장하고 시작한다. 이후 주의해야 할 점은 모래성은 한번에 무너진다는 점과, 종료 조건은 맵이 더 이상 변화하지 않는 시점이라는 점이다. 

 파도가 칠 때는 매번 큐의 크기를 구한 뒤 큐의 크기만큼만 동작을 해야한다. 그 이유는 파도가 치는 시간을 계산해야하기 때문인데 한 턴이 끝난 후(큐의 크기만큼 동작한 것)에는 시간을 증가시켜주어야 한다. 또한 한번 탐색한 모래성이 없는 노드는 다시 탐색할 필요가 없기 때문에 새롭게 모래성이 없어진 좌표만 큐에 삽입해주어야 한다. 최종적으로 큐에 어떤 값도 쌓여있지 않은 경우는 더 이상 어떤 변화도 일어나지 않는다는 의미이기 때문에 이럴때는 누적 시간을 return 하고 종료해주어야 한다.

 

 이번 문제는 아이디어 자체는 그렇게 어렵지 않았지만 한 턴에 이전에 큐에 쌓인 크기만큼만 동작해야 한다는 점을 떠올리기는 어려웠던 것 같다. 체크해두고 복습할 문제로 남겨두어야겠다.