PS][java][완전탐색][BFS]/[벽 부수고 이동하기4]

boj-java-16946.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n,m;
    static int[][] map;
    static int[][] num;
    static ArrayList<Integer> arr;
    static boolean[][] visit;
    static Queue<Point> q, q2;
    static class Point{
        int r,c,l;//row column length
        Point(int r, int c, int l){
            this.r = r;
            this.c = c;
            this.l = l;
        }
    }
    static int[] dr = {0,0,1,-1};
    static int[] dc = {1,-1,0,0};

    static int bfs(int r, int c,int key){
        int dist = 1;
        q2.offer(new Point(r,c,0));
        visit[r][c] = true;
        while(!q2.isEmpty()){
            Point curr = q2.poll();
            num[curr.r][curr.c] = key;
            for(int j=0; j<4; j++){
                int nr = curr.r + dr[j];
                int nc = curr.c + dc[j];
                if(nr<0 || n<=nr || nc<0 || m<=nc) continue;
                if(map[nr][nc] == 0 && !visit[nr][nc]){
                    visit[nr][nc] = true;
                    q2.offer(new Point(nr,nc,0));
                    dist++;
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        num = new int[n][m];
        visit = new boolean[n][m];
        q = new LinkedList<>();
        q2 = new LinkedList<>();
        for(int i=0; i< n; i++){
            String line = br.readLine();
            for(int j=0; j<m; j++){
                map[i][j] = line.charAt(j)-'0';
            }
        }
        arr = new ArrayList<>();
        arr.add(0);
        int key =0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] == 0 && !visit[i][j]) {
                    key++;
                    int len = bfs(i,j,key);
                    arr.add(len);
                    q.offer(new Point(i,j,len));
                }
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] > 0){
                    HashSet<Integer> s = new HashSet<>();
                    for(int k=0; k<4; k++){
                        int nr = i + dr[k];
                        int nc = j + dc[k];
                        if(nr<0 || n<=nr || nc<0 || m<=nc) continue;
                        s.add(num[nr][nc]);
                    }
                    Iterator<Integer> it = s.iterator();
                    while(it.hasNext()){
                        map[i][j] += arr.get(it.next());
                    }
                }
            }
        }

        for(int i=0; i< n; i++){
            for(int j=0; j<m; j++){
                System.out.print(map[i][j]%10);
            }
            System.out.println();
        }
    }
}