문제

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

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

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

---

입력

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

---

출력

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

---

풀이

접근방법

시간제한 2초, 메모리512MB, N과 M 이 (1 ≤ N,M ≤ 1,000)이다.
메모리가 넉넉하므로 메모리를 잘 쓰자 라는 생각을 가지고 문제에 임한다.

입력
3 3
101
010
101

1. 각 좌표마다 벽을 부숴보고 계산을 해본다 라고 가정을 하자. 1행 1열을 계산할때와 1행 3열을 계산할때 1행 2열의 결과가 둘 다 필요하다는것을 알 수 있다. 이처럼
   각 좌표마다 모두 계산을 한다면 중복계산이 많이 발생한다.

2. 이미 벽이 없는 지점 (0인곳) 에서 탐색을 시작해서 해당 지점에서 탐색할 수 있는 칸이 몇 칸 인지 모두 계산을 한다. 그 다음 벽이 있는 지점(1인곳)을 순회하며 상하좌우를 살피며 각각 몇 칸을 갈 수 있는지 미리 계산된 값을 더한다.

• 주의할 점
  입력 아래와 같다면, 1의 위쪽에서 연결된 0들과 1의 오른쪽에서 연결된 0들이 같은 그룹이다. 중복해서 더하지 않도록 주의하자.
  3 3
  000
  000
  100

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Main {
	static class Pair {
		int x;
		int y;

		Pair(int a, int b) {
			x = a;
			y = b;
		}
	}

	static int N, M;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int[][] map, visit;
	static StringBuilder sb;
	static String[] splitedLine;
	static Map<Integer, Integer> countMap = new HashMap<>();

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();

		// 입력부
		splitedLine = in.readLine().split(" ");
		N = Integer.parseInt(splitedLine[0]);
		M = Integer.parseInt(splitedLine[1]);

		map = new int[N][M];
		visit = new int[N][M];

		for (int i = 0; i < N; ++i) {
			String line = in.readLine();
			for (int j = 0; j < M; ++j) {
				map[i][j] = line.charAt(j) - '0';
			}
		}

		// 로직
		int groupId = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				if (visit[i][j] == 0 && map[i][j] == 0) {
					groupId++;
					bfs(i, j, groupId);
				}
			}
		}

		// 출력부
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				if (map[i][j] == 1) {
					int c = 1;
					Set<Integer> set = new HashSet<>();
					for (int d = 0; d < 4; ++d) {
						int nextX = i + dx[d];
						int nextY = j + dy[d];
						if (isInRange(nextX, nextY) && visit[nextX][nextY] != 0)
							set.add(visit[nextX][nextY]);
					}
					for (int key : set) {
						c += countMap.get(key);
					}
					sb.append(c%10);
				} else {
					sb.append("0");
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

	private static void bfs(int x, int y, int groupId) {
		Queue<Pair> q = new ArrayDeque<>();
		q.add(new Pair(x, y));
		visit[x][y] = groupId;
		int count = 0;
		while (!q.isEmpty()) {
			Pair p = q.poll();
			count++;
			for (int i = 0; i < 4; ++i) {
				int nextX = p.x + dx[i];
				int nextY = p.y + dy[i];
				if (isInRange(nextX, nextY) && map[nextX][nextY] == 0 && visit[nextX][nextY] == 0) {
					visit[nextX][nextY] = groupId;
					q.add(new Pair(nextX, nextY));
				}
			}
		}
		countMap.put(groupId, count);
	}

	private static boolean isInRange(int nextX, int nextY) {
		if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M)
			return true;
		else
			return false;
	}
}