[SWEA_1907 - JAVA] 모래성 쌓기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PNx_KACIDFAUq

SW Expert Academy

 

 

풀이

상당히 오래걸린 문제.
처음 풀이는 8방탐색으로 완전탐색을 하는 것이었다.
7개의 testcase 중 3개를 맞은 뒤, 시간초과에 걸려 터져버렸다.
파도수가 200 이상이면 2초(1000*1000*200) 이상이 걸려 시간초과.
(제출 결과 : 7개 testcase 중 3개 이후 시간초과)
기존 풀이 방식으로는 시간초과를 통과 할 수 없으므로, 큐와 bfs형식으로 재풀이.

기존풀이가 모래성을 위주로 주변의 모래가 없는 경우를 탐색했다면,
같은크기의 map을 만들어 반대로 모래가 없는경우 주변의 모래성에 모래가 없는 경우를 카운트.

좌표 관리를 편하게 하기위해 pair 클래스를 생성.
모래성이 없는 경우를 담을 q 생성.
wave로 인하여 부서질 모래성을 담을 nq 생성.

 

자세한 풀이 순서

 

1. map과 같은 크기의 2차원배열 crack 생성.(모래성 근처의 모래성이 없는 경우를 담을 배열)
2. 입력을 받으면서 모래성이 없는 경우를 visited = true를 한 뒤 큐에 pair형태로 삽입.('.'를 Int 0 으로 치환)
3. wave 함수 호출
4. 큐가 빌때까지 돌며 팔방탐색.
5. 팔방 탐색을 하는 동안 범위와 방문여부 관리
6. 팔방 탐색 동안 주변에 모래성이 있다면 crack 배열 모래성 위치에 +1
7. crack의 모래성위치 값이 map의 모래성 값과 같거나 커진다면  nq에 삽입 후 방문 체크.
8. 팔방탐색이 끝난 후 부서질 모래성인 nq가 빌때까지 while
9. nq가 비어있지 않다면 count+1.(wave의 횟수)
10. nq가 빌때까지 map의 모래성을 0으로 치환 후 모래성이 없는 경우인 q에 삽입.
11. 이후 다시 q가 빌때까지 반복.( 4번 순서로 간다.)
12. q와 nq가 빌때, while문을 탈출
13. 결과값 출력.

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
// 모래 정보
class pair {
    int row;
    int col;
 
    public pair(int row, int col) {
        super();
        this.row = row;
        this.col = col;
    }
 
}
 
public class Solution {
 
    static int H, W, count;
    static int[][] map; // 입력 받는 map
    static int[][] crack; // 근처에 모래가 없는 수
    static boolean[][] visited; // 방문 여부
    static int[] dy = { -1, -1, -1, 0, 1, 1, 1, 0 }; // 좌상부터 시계방향
    static int[] dx = { -1, 0, 1, 1, 1, 0, -1, -1 };
    static Queue<pair> q; // 모래성이 없는 경우
    static Queue<pair> nq; // 모래성이 없어질 경우
 
    // 범위 검사
    public static boolean isValid(int i, int j) {
        if (i < 0 || j < 0 || i >= H || j >= W) {
            return true;
        }
        return false;
    }
 
    // wave
    public static void wave() {
        while (!q.isEmpty()) {
            int y = q.peek().row;
            int x = q.peek().col;
            q.poll();
 
            // 8방 탐색
            for (int i = 0; i < 8; i++) {
                int nexty = y + dy[i];
                int nextx = x + dx[i];
 
                // 범위 밖 && 방문 여부
                if (isValid(nexty, nextx) || visited[nexty][nextx])
                    continue;
 
                // 모래성이 있는 경우
                if (map[nexty][nextx] != 0) {
                    crack[nexty][nextx] += 1; // 근처에 모래가 있지 않는 갯수
 
                    // 모래성이 무너지는 경우
                    if (crack[nexty][nextx] >= map[nexty][nextx]) {
                        nq.offer(new pair(nexty, nextx)); // 큐에 삽입
                        visited[nexty][nextx] = true; // 방문 체크
                    }
                }
            }
 
            if (q.isEmpty()) { // 검사가 끝났다면
                if (!nq.isEmpty()) // count + 1
                    count++;
 
                while (!nq.isEmpty()) { // 무너질 모래성들의 경우
                    int ny = nq.peek().row;
                    int nx = nq.peek().col;
                    nq.poll();
 
                    map[ny][nx] = 0; // 모래성이 무너짐
                    q.offer(new pair(ny, nx)); // 무너진 모래성 큐에 삽입
                }
            }
 
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for (int test = 1; test <= tc; test++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            map = new int[H][W];
            crack = new int[H][W];
            visited = new boolean[H][W];
 
            // 초기화
            q = new LinkedList<pair>();
            nq = new LinkedList<pair>();
            count = 0;
            String str;
            char c;
 
            for (int i = 0; i < H; i++) {
                str = br.readLine();
                for (int j = 0; j < W; j++) {
                    c = str.charAt(j);
                    if (c == '.') {
                        map[i][j] = 0;
                        q.offer(new pair(i, j)); // 큐에 삽입
                        visited[i][j] = true; // 방문 체크
                    } else
                        map[i][j] = c - '0';
                }
            }
            // ======================== 입력 ========================
 
            wave();
            System.out.println("#" + test + " " + count);
        }
    }
 
}