문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

벽을 부수고 이동할 수 있는 곳으로 변경한다.
그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

예제1 - 입력

3 3
101
010
101

예제1 - 출력

303
050
303

예제2 - 입력

4 5
11001
00111
01010
10101

예제2 - 출력

46003
00732
06040
50403

제출 코드

import java.io.*;
import java.lang.reflect.Parameter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[][] map, visited;
    static int n, m, group;
    static HashMap<Integer, Integer> hm;
    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];
        for (int i = 0; i < n; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                map[i][j] = input[j] - '0';
            }
        }
        br.close();
        hm = new HashMap<>();
        visited = new int[n][m];
        group = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0 && visited[i][j] == 0) {
                    hm.put(group, bfs(group, i, j));
                    group++;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1) {
                    sb.append(checking(i, j));
                }
                else {
                    sb.append("0");
                }
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
    static int checking (int nx, int ny) {
        int cnt = 1;
        int[] mx = {-1, 1, 0, 0};
        int[] my = {0, 0, -1, 1};

        boolean[] used = new boolean[group];
        for (int i = 0; i < mx.length; i++) {
            int tx = nx + mx[i];
            int ty = ny + my[i];

            if ((tx >= 0 && tx < n) && (ty >= 0 && ty < m)) {
                if (map[tx][ty] == 0) {
                    int gnum = visited[tx][ty];
                    if (!used[gnum]) {
                        cnt += hm.get(gnum);
                        used[gnum] = true;
                    }
                }
            }
        }
        return cnt % 10;
    }
    static int bfs (int group, int nx, int ny) {
        int cnt = 1;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {nx, ny});
        visited[nx][ny] = group;

        int[] mx = {-1, 1, 0, 0};
        int[] my = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
           int[] now = queue.poll();

            for (int i = 0; i < mx.length; i++) {
                int tx = now[0] + mx[i];
                int ty = now[1] + my[i];

                if ((tx >= 0 && tx < n) && (ty >= 0 && ty < m)) {
                    if (map[tx][ty] == 0 && visited[tx][ty] == 0) {
                        queue.offer(new int[] {tx, ty});
                        visited[tx][ty] = group;
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
}

참고링크 : https://settembre.tistory.com/298