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

import java.io.*;
import java.util.*;

class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    static int[] numx= {-1,1,0,0};
    static int[] numy= {0,0,-1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());
        //맵초기화
        int[][] map=new int[n+1][m+1];
        for(int i=1; i<=n; i++){
            String a=br.readLine();
            for(int j=1; j<=m; j++){
                map[i][j]=a.charAt(j-1)-'0';
            }
        }

        Queue<Point> que;
        ArrayList<Point> near;
        //영역을 더한 정점들을 구분하기위함.
        int[][] mid=new int[n+1][m+1];
        boolean[][] visit=new boolean[n+1][m+1];
        //0지점들 모아서, 접점 1들에 더해주기
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                //방문안한 정점일때 영역들 모아야함
                if(map[i][j]==0 && !visit[i][j]){
                    que=new LinkedList<>();
                    near=new ArrayList<>();

                    que.offer(new Point(j,i));
                    visit[i][j]=true;
                    //영역의 합
                    int totalP=1;
                    //bfs로 영역의 합구하기. 벽이면 near에 추가
                    while(!que.isEmpty()){
                        Point temp=que.poll();

                        for(int k=0; k<4; k++){
                            int tx=temp.x+numx[k];
                            int ty=temp.y+numy[k];

                            if(tx<1 || tx>m || ty<1 || ty>n || visit[ty][tx]){
                                continue;
                            }
                            //0이면 영역더하고, que추가로 영역 넓히며 파악
                            if(map[ty][tx]==0){
                                totalP++;
                                visit[ty][tx]=true;
                                que.offer(new Point(tx,ty));
                            }
                            //벽인 곳이면, 접점리스트추가
                            else{
                                near.add(new Point(tx,ty));
                            }
                        }
                    }
                    //접점들에 영역추가. 이중체크 막기위해 mid에 해당 접점값 저장.
                    //추가할때 동일값== 이미추가 다르면 추가해야됨.
                    //체크포인트는 접점y * 10000 + 접점x값
                    int check = i*10000 + j;
                    for(int k=0; k<near.size(); k++){
                        Point temp=near.get(k);
                        if(mid[temp.y][temp.x]==check){
                            continue;
                        }
                        map[temp.y][temp.x]= (map[temp.y][temp.x]+totalP);
                        mid[temp.y][temp.x]=check;
                    }

                }
            }
        }
        //%10을 중간에 하면, 실제로 벽이지만, 영역으로 오해가능 따라서 마지막에 답 구할 때 %10하기.
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                bw.write(map[i][j]%10+"");
            }
            bw.write("\n");
        }
        bw.flush();
    }
}