[백준] 16946번 벽 부수고 이동하기4

문제 설명

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

문제 풀이

• BFS 문제이다.
• 이 문제에서 가장 신경써야할 부분은 각 벽을 부수고 빈칸을 세줄 때 다른 벽에 대해 특정 빈칸을 중복해서 세지 않아야 한다는 점이다.
• 각 벽에 대해 이동가능한 칸을 계산하기에 앞서서 맵 전체를 순회하며 빈칸이 나오면 해당 빈칸을 그룹화하고 그룹별로 이동가능한 칸 갯수를 미리 계산해준다.

[입력맵]       [그룹맵]
11001         00110      그룹1 : 2개, 그룹2 : 3개
00111    ->   22000      그룹3 : 1개, 그룹4 : 1개
01010 		  20304      그룹5 : 1개, 그룹6 : 1개 
10101         05060

• 위 정보를 토대로 특정 벽에 대해 4방향 빈칸을 확인하여 그룹이 중복되지 않으면 해당 그룹의 이동가능한 칸 갯수를 더해주면 된다.

+) 그동안 기본 자바 입출력(Scanner)를 사용했는데 해당 방식으로 출력을 하면 시간초과가 발생하여 BufferdWriter로 최적화가 필요했다.. 자바 입출력 방식에 대해서는 아래 포스트 참조

• https://wonit.tistory.com/559

소스 코드 (JAVA)

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

    public static class Point {
        int x, y;

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

    public static int N, M;
    public static int[][] map = new int[1000][1000];         //빈칸 : 0, 벽 : -1
    public static int[][] grpMap = new int[1000][1000];
    public static List<Point> wallList = new ArrayList<>();
    public static List<Integer> cellCnt = new ArrayList<>(); //그룹별 cell 갯수
    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};

    public static void makeResult() {
        //각 벽에 대해 부순후 이동가능한 칸 갯수를 map에 입력해줌
        for(int i = 0; i < wallList.size(); i++) {
            Point cur = wallList.get(i);
            int totalCnt = 1;
            HashMap<Integer, Integer> hashMap = new HashMap<>();
            for (int d = 0; d < 4; d++) {
                int X = cur.x + dx[d];
                int Y = cur.y + dy[d];
                if (X < 0 || Y < 0 || X >= N || Y >= M || map[X][Y] != 0) continue;
                if (hashMap.containsKey(grpMap[X][Y])) continue;
                hashMap.put(grpMap[X][Y], 1);
                totalCnt += cellCnt.get(grpMap[X][Y]);
            }
            map[cur.x][cur.y] = totalCnt % 10;
        }
    }

    public static void grouping() {
        Queue<Point> queue = new LinkedList<>();
        int grpIndex = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == -1) continue;
                if (grpMap[i][j] != 0) continue;
                //해당 셀에서 그룹핑 시작
                grpIndex++;
                int totalCnt = 0;

                //BFS
                totalCnt++;
                grpMap[i][j] = grpIndex;
                queue.add(new Point(i, j));
                while(!queue.isEmpty()) {
                    Point cur = queue.poll();
                    for (int d = 0; d < 4; d++) {
                        int X = cur.x + dx[d];
                        int Y = cur.y + dy[d];
                        if (X < 0 || Y < 0 || X >= N || Y >= M || grpMap[X][Y] != 0 || map[X][Y] == -1) continue;
                        totalCnt++;
                        grpMap[X][Y] = grpIndex;
                        queue.add(new Point(X, Y));
                    }
                }
                cellCnt.add(totalCnt);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); M = sc.nextInt();
        for (int i = 0; i < N; i++) {
            String tmp = sc.next();
            for (int j = 0; j < M; j++) {
                if (tmp.charAt(j) == '0') map[i][j] = 0;
                if (tmp.charAt(j) == '1') {
                    wallList.add(new Point(i,j));
                    map[i][j] = -1;
                }
            }
        }
        //그룹핑
        cellCnt.add(0);
        grouping();
        //결과 계산
        makeResult();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++)
                sb.append(map[i][j]);
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}