(JAVA) 백준 10711번 : 모래성

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

10711번: 모래성

 

 

시간초과 때문에 꽤나 애먹었던 문제..

 

 

 

핵심 키워드는 이거다.

 

"모래성이 아닌 빈 모래를 활용하라."

 

 

 

BFS, DFS, Deque, 2중 for문 등등

 

여러 방법을 동원해봤지만

 

테스트케이스는 통과하는데 시간은 초과되는 문제가 계속 일어났다.

 

 

 

그러던 중, 

 

번뜩 떠올랐다.

 

 

 

 

"굳이 파도 한 번마다 모래성 주위 8방향을 탐색하며 갯수 셀 필요가 있을까?"

 

"모래성은 어차피 줄어들고, 빈 모래는 늘어나니까."

 

 

 

"BFS를 사용해서 빈 모래 근방 모래성들 크기를 1씩 떨어뜨리면 되지 않을까?"

 

"어차피 한 번만 빈 모래 사용하면 이후에는 굳이 사용할 필요가 없지. 빈 모래는 다시 찾지 않아도 되니."

 

 

저 4문장을 보고 나면

 

대충 알고리즘과 해결방법이 떠오를 것이다.

 

 

 

그렇지만 

필자가 설명을 잘 못한 것일수도 있기에

 

필자의 매커니즘과 소스코드를 첨부하겠다.

 

매커니즘

---

1)  입력 값 int 2차원 배열에 입력

 

 

2)  입력 값 중 빈 모래 발견 -> 빈 모래의 x ,y 좌표 값 별도 Queue에 담기

*** 당연히 x, y 좌표를 담는 별도 Class를 생성해야 함

 

 

3)  빈 모래 empty 까지 Queue에서 꺼내기

*** 중요한 것은 처음에 queue의 크기를 가져와야 한다. 파도가 치는 시간을 파악해야 하니.

*** 그래서 empty 까지 계속 꺼낼 때 마다 count하면서 처음에 저장한 queue의 크기와 비교한다.

같아질 경우에는 파도가 한번 휩쓸고 지나간 경우이므로 다시 queue의 크기를 가져오고 empty 까지 위 과정을 반복 진행한다.

 

 

4)  꺼낸 빈 모래 주위 8곳 크기 -1 진행

 

 

4 - 1)  주위 크기 중 0이 되는 모래가 있으면 빈 모래(. => 필자는 -1로 정의) 로 바꾸고 빈 모래 좌표 Queue에 넣기

 

 

5)  위 과정을 Queue가 empty 될 때 까지 반복 => empty는 수렴한 경우이므로 종료 후 경과 시간 출력

 

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	// 10711번 : 모래성
	// 탐색 문제
	public class p10711 {
	static int[][] map;
	static boolean[][] boolMap;
	static int[] moveX = {0, 1, 1, 1, 0, -1, -1, -1};
	static int[] moveY = {-1, -1, 0, 1, 1, 1, 0, -1};
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int h = Integer.valueOf(st.nextToken());
	int w = Integer.valueOf(st.nextToken());
	map = new int[h + 1][w + 1]; // 인덱스 : 1 ~ h , 1 ~ w
	boolMap = new boolean[h + 1][w + 1];
	Queue<EmptySand> mainQueue = new LinkedList<EmptySand>();
	// INPUT 값 입력받음
	for(int y = 1; y <= h; y++) {
	String line = br.readLine();
	for(int x = 1; x <= w; x++) {
	char num = line.charAt(x - 1);
	if(num == '.') { // . == -1
	map[y][x] = -1;
	boolMap[y][x] = true;
	mainQueue.offer(new EmptySand(x, y));
	}
	else {
	map[y][x] = Character.getNumericValue(num);
	}
	}
	}
	int time = comeToWave(h, w, mainQueue);
	System.out.println(time);
	}
	// 파도가 친다
	static int comeToWave(int h, int w, Queue<EmptySand> mainQueue) {
	int time = -1;
	// 빈 모래들 하나하나 파도 작업
	int len = mainQueue.size();
	int nowCount = 0;
	while(!mainQueue.isEmpty()) {
	EmptySand emptySand = mainQueue.poll();
	nowCount++;
	// 빈 모래 주위 모래성 깎기
	ArrayList<EmptySand> list = setEmptySand(emptySand.x, emptySand.y, h, w);
	if(!list.isEmpty()) {
	for(EmptySand ele : list) {
	mainQueue.add(ele);
	}
	}
	if(nowCount == len) {
	time++;
	nowCount = 0;
	len = mainQueue.size();
	}
	}
	return time;
	}
	// 빈 모래 주위 모래 깎고, 빈 모래가 생기면 그걸 반환하는 함수
	static ArrayList<EmptySand> setEmptySand(int x, int y, int h, int w) {
	ArrayList<EmptySand> list = new ArrayList<EmptySand>();
	for(int i = 0; i < moveY.length; i++) {
	int nextX = x + moveX[i];
	int nextY = y + moveY[i];
	if((nextX < 1 || nextX > w) || (nextY < 1 || nextY > h)) {
	continue;
	}
	if(map[nextY][nextX] > 0) {
	map[nextY][nextX]--;
	}
	if(map[nextY][nextX] == 0 && !boolMap[nextY][nextX]) {
	map[nextY][nextX] = -1;
	boolMap[nextY][nextX] = true;
	list.add(new EmptySand(nextX, nextY));
	}
	}
	return list;
	}
	}
	class EmptySand {
	int x;
	int y;
	EmptySand(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}

view raw p10711.java hosted with ❤ by GitHub