1907. 모래성 쌓기 (D5)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PNx_KACIDFAUq&categoryId=AV5PNx_KACIDFAUq&categoryType=CODE

< 입력 >

맵의 세로 길이 H, 가로 길이 W (1<= H,W<=1,000)

< 출력 >

모래성의 상태가 변하지 않기 시작하는 파도 횟수

< 풀이 >

모 기업 테스트 기출과 비슷한 문제..읍읍

파도가 1번 칠 때마다 맵의 상태가 변한다.

전체를 탐색할 경우 1,000 * 1,000 * 파도횟수 만큼의 시간이 걸릴 수 있다.

즉, 상태 변화가 일어나지 않을 때까지 전체를 계속해서 탐색하며 변화시키면 풀 수 없다는 뜻 !

최적화가 필요한 문제이다.

그렇다면, 맵 전체를 탐색하지 않고 상태를 변화시킬 수 있는 방법이 뭐가 있을까?

더이상 변화가 없을 때까지 이번에 무너지는 모래성들과 다음 상태에서 무너질 모래성들만 보는 것이다.

이런 생각은 했는데 어떻게 구현을 해야할까?

"현재 무너지는 모래성들의 주변을 살피며 새롭게 무너질 모래성들을 찾는다."

이 개념을 구현하기 위해 큐(Queue)를 이용할 것이다.

먼저, 전체를 탐색하며 이번에 무너질 모래성들을 큐에 담는다.

위와 같은 상태가 만들어졌으면 큐의 크기만큼 탐색을 한다.

탐색을 통해 이번에 무너질 모래성을 하나씩 빼면서

주변 8칸의 값을 바꿔준다.

바꿔주는 과정에서 주변 8칸 중 무너지게 될 모래성이 생길 수 있다.

이는 "이 모래성이 다음 파도 때 무너질 것이다."라는 뜻이다.

'이번에 무너질 모래성'들을 확인하며 '다음에 무너질 모래성'들을 찾는 과정인 것이다.

위 그림과 같이 다음에 무너질 모래성들을 새롭게 큐에 넣는다.

큐에 '다음에 무너질 모래성'만 남아있을 때까지 진행하는 것이 파도 1번에 대한 한 사이클이다.

이 과정을 큐가 비어있을 때까지 진행한다.

사이클을 진행했음에도 큐가 비어있다는 것은 다음에 무너질 모래성이 없다.

즉, 찾고 있던 더이상 상태가 변하지 않는 지점을 찾은 것이다.

이제 몇 번의 사이클을 진행했는지 출력하면 끝 !

---

- 소스 코드 -

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int map[][];
    static int dmg[][];
    static Queue<point> myQ;
 
    static int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
    static int dy[] = { 1, 0, -1, 0, -1, 1, 1, -1 };
 
    static class point {
        int x;
        int y;
 
        point() {
            x = 0;
            y = 0;
        }
 
        point(int a, int b) {
            x = a;
            y = b;
        }
    };
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int test_case = 1; test_case <= T; test_case++) {
            myQ = new LinkedList<>();
            st = new StringTokenizer(br.readLine());
            int height = Integer.parseInt(st.nextToken());
            int width = Integer.parseInt(st.nextToken());
            map = new int[height][width];
            dmg = new int[height][width];
            for (int i = 0; i < height; i++) {
                st = new StringTokenizer(br.readLine());
                String temp = st.nextToken();
                for (int j = 0; j < width; j++) {
                    if (temp.charAt(j) >= '0' && temp.charAt(j) <= '9') {
                        map[i][j] = (int) temp.charAt(j) - (int) '0';
                    } else {
                        map[i][j] = 0;
                    }
                }
            }
 
            for (int i = 1; i < height-1; i++) {
                for (int j = 1; j < width-1; j++) {
                    for (int k = 0; k < 8; k++) {
                        if (map[i + dx[k]][j + dy[k]] == 0) {
                            dmg[i][j]++;
                        }
                    }
                    if (map[i][j]!=0&&map[i][j] <= dmg[i][j]) {
                        myQ.add(new point(i, j));
                    }
                }
            }
            int tryCount = 0;
            while (!myQ.isEmpty()) {
                tryCount++;
                int t = myQ.size();
 
                for (int i = 0; i < t; i++) {
                    point p = myQ.poll();
                    for (int j = 0; j < 8; j++) {
                        if (map[p.x + dx[j]][p.y + dy[j]] > dmg[p.x + dx[j]][p.y + dy[j]]) {
                            dmg[p.x + dx[j]][p.y + dy[j]]++;
                        } else {
                            continue;
                        }
                        if (map[p.x + dx[j]][p.y + dy[j]] <= dmg[p.x + dx[j]][p.y + dy[j]]) {
                            myQ.add(new point(p.x + dx[j], p.y + dy[j]));
                        }
                    }
                }
            }
            System.out.printf("#%d %d\n",test_case,tryCount);
        }
    }
}

---