벽 부수고 이동하기 4

문제
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

풀이

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


public class Main {
	static int[][] graph;
	public static final int[] dx = { -1, 0, 0, 1 };
	public static final int[] dy = { 0, -1, 1, 0 };
	static int N, M;
	static int count = 0;

	static void DFS(int condition, int r, int c, boolean[][] visited, int num) {
		if (r < 0 || r >= N)
			return;
		if (c < 0 || c >= M)
			return;
		if (graph[r][c] != condition)
			return;
		if (visited[r][c])
			return;
		visited[r][c] = true;
		group[r][c] = num;
		count++;
		DFS(condition, r - 1, c, visited, num);
		DFS(condition, r + 1, c, visited, num);
		DFS(condition, r, c - 1, visited, num);
		DFS(condition, r, c + 1, visited, num);

	}

	static void countMap() {
		boolean[][] visited = new boolean[N][M];
		int num = 0;
		for (int r = 0; r < N; ++r)
			for (int c = 0; c < M; ++c) {
				if (visited[r][c] == false) {
					int condition = graph[r][c];
					if (condition == 0) {
						count = 0;
						num++;
						DFS(condition, r, c, visited, num);
						group_count[num] = count;
					}
				}

			}
		return;
	}

	static int[][] group;
	static int[] group_count;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		N = Integer.parseInt(tokenizer.nextToken());
		M = Integer.parseInt(tokenizer.nextToken());
		graph = new int[N][M];
		group = new int[N][M]; // 좌표 빈칸이 어디 그룹에 들어가는지
		group_count = new int[N * M]; // 그룹마다 갈수있는 칸 수
		int[][] d = new int[N][M];
		for (int i = 0; i < N; i++) {
			String s = reader.readLine();
			for (int j = 0; j < M; j++)
				graph[i][j] = s.charAt(j) - '0';
		}
		countMap();
		int last = 0;
		for (int r = 0; r < N; ++r) {
			for (int c = 0; c < M; ++c) {
				last=0;
				if (graph[r][c] == 1) {
					for (int k = 0; k < 4; k++) {
						int nx = r + dx[k];
						int ny = c + dy[k];
						if (nx < 0 || nx >= N || ny < 0 || ny >= M)
							continue;
						if (group[nx][ny] > last)
						{
							last =group[nx][ny];
							d[r][c] += group_count[group[nx][ny]];
						}

					}
					System.out.print((d[r][c] + 1)%10);
				} else
					System.out.print(d[r][c]%10);

			}
			System.out.println();

		}

	}
}

결과는 틀렸습니다. ㅜ
11001
00111
01010
10101

빈칸인 부분을 bfs로 그룹화를 한다.

00110
22000
20304
05060

그 그룹마다 이동할수 있는 칸을 저장해둔다.

틀린 이유는

if (group[nx][ny] > last)
{
	last =group[nx][ny];
	d[r][c] += group_count[group[nx][ny]];
}

r,c 좌표에서 주변에 무슨 그룹이 있는지 확인할때
중복되는 그룹을 거르기 위해 만들어 놨는데
중복을 업ㄱ애기 위해서
처음에 나도 hash를 생각하긴했다.
간편한 방법이 없을까 하다가 나온 방법 예제까지는 잘 풀리지만
반례상황이 존재 했다.
결국 좀더 확실한 hash를 사용해서 다시 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static int[][] graph;
	public static final int[] dx = { -1, 0, 0, 1 };
	public static final int[] dy = { 0, -1, 1, 0 };
	static int N, M;
	static int count = 0;

	static void DFS(int condition, int r, int c, boolean[][] visited, int num) {
		if (r < 0 || r >= N)
			return;
		if (c < 0 || c >= M)
			return;
		if (graph[r][c] != condition)
			return;
		if (visited[r][c])
			return;
		visited[r][c] = true;
		group[r][c] = num;
		count++;
		DFS(condition, r - 1, c, visited, num);
		DFS(condition, r + 1, c, visited, num);
		DFS(condition, r, c - 1, visited, num);
		DFS(condition, r, c + 1, visited, num);

	}

	static void countMap() {
		boolean[][] visited = new boolean[N][M];
		int num = 0;
		for (int r = 0; r < N; ++r)
			for (int c = 0; c < M; ++c) {
				if (visited[r][c] == false) {
					int condition = graph[r][c];
					if (condition == 0) {
						count = 0;
						num++;
						DFS(condition, r, c, visited, num);
						group_count[num] = count;
					}
				}

			}
		return;
	}

	static int[][] group;
	static int[] group_count;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		N = Integer.parseInt(tokenizer.nextToken());
		M = Integer.parseInt(tokenizer.nextToken());
		graph = new int[N][M];
		group = new int[N][M]; // 좌표 빈칸이 어디 그룹에 들어가는지
		group_count = new int[(N * M)+1]; // 그룹마다 갈수있는 칸 수
		for (int i = 0; i < N; i++) {
			String s = reader.readLine();
			for (int j = 0; j < M; j++)
				graph[i][j] = s.charAt(j) - '0';
		}
		countMap();
		StringBuilder builder = new StringBuilder();

		for (int r = 0; r < N; ++r) {
			for (int c = 0; c < M; ++c) {
				if (graph[r][c] == 0) {
					builder.append("0");
				} else if (graph[r][c] == 1) {
					HashSet<Integer> near = new HashSet<>();
					for (int k = 0; k < 4; k++) {
						int nx = r + dx[k];
						int ny = c + dy[k];
						if (nx < 0 || nx >= N || ny < 0 || ny >= M)
							continue;
						if (graph[nx][ny] == 0) {
							near.add(group[nx][ny]);
						}
					}
					int ans = 1;
					for (int g : near) {
						ans += group_count[g];
					}
					builder.append(ans%10);
				}
			}
			builder.append("\n");
		}
		System.out.println(builder);
	}
}