BOJ 16946 G2 벽부수고 이동하기 4 [JAVA]

문제 링크 : https://www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

문제

------------------------

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

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

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

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

 

입력

------------------------

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

출력

------------------------

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

 

 

예제 입력 2 설명

미리 0의 칸 수를 계산한다.

1의 자리에서 4방 탐색하여 0의 자리에 존재하는 해당 0공간 갯수 값을 모두 더한다.

 

유의점

위와 같이 한 점에서 상,좌는 같은 0공간을 공유하므로 더하는 것은 한번만 수행한다.

 

JAVA 코드 보기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// mem : 132232kb, time : 1048ms
public class BOJ_16946_G2_벽부수고이동하기4 {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);

		byte read() throws IOException {
			if (bufferPos == bufferState) {
				bufferState = dis.read(buffer, bufferPos = 0, bfs);

				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];

		}

		int nextInt() throws IOException {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}
	}

	static Queue<int[]> q = new LinkedList<int[]>();
	static Queue<int[]> rslt = new LinkedList<int[]>();

	static int[][] dydx = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int[][] bd, set, answer;
		boolean[][] visited;
		int row, col;
		row = Integer.parseInt(st.nextToken());
		col = Integer.parseInt(st.nextToken());
		bd = new int[row][col];
		set = new int[row][col];
		answer = new int[row][col];
		visited = new boolean[row][col];
		int[][] numbering = new int[row][col];
		int[][][] numberingCheck = new int[row][col][4];
		for (int i = 0; i < row; i++) {
			Arrays.fill(set[i], -1);
		}

		for (int i = 0; i < row; i++) {
			char[] tmp = br.readLine().toCharArray();
			for (int j = 0; j < col; j++) {
				bd[i][j] = tmp[j] - '0';
				Arrays.fill(numberingCheck[i][j], -1);
			}
		}
		int stack = 0;
		int number = -1;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				// 검사하지 않았고 0번자리일 경우
				if (set[i][j] == -1 && bd[i][j] == 0) {
					number++;
					stack = 1;
					q.add(new int[] { i, j });
					rslt.add(new int[] { i, j });
					visited[i][j] = true;
					while (!q.isEmpty()) {
						int[] crntYX = q.poll();
						int crntY = crntYX[0];
						int crntX = crntYX[1];

						for (int k = 0; k < 4; k++) {
							int nextY = crntY + dydx[k][0];
							int nextX = crntX + dydx[k][1];
							if (nextY < 0 || nextX < 0 || row == nextY || col == nextX)
								continue;

							if (!visited[nextY][nextX] && bd[nextY][nextX] == 0) {
								stack++;
								visited[nextY][nextX] = true;
								q.add(new int[] { nextY, nextX });
								rslt.add(new int[] { nextY, nextX });
							}

						}

					}
				}
				while (!rslt.isEmpty()) {
					int tmp[] = rslt.poll();
					set[tmp[0]][tmp[1]] = stack;
					numbering[tmp[0]][tmp[1]] = number;
				}

			}

		}
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (bd[i][j] == 1) {
					answer[i][j]++;
					LOOP: for (int k = 0; k < 4; k++) {
						int nextY = i + dydx[k][0];
						int nextX = j + dydx[k][1];

						if (nextY < 0 || nextX < 0 || row == nextY || col == nextX)
							continue;
						if (bd[nextY][nextX] == 0) {

							number = numbering[nextY][nextX];

							// 4개 저장 포인트 중에 중복되는 게 있는지 검사
							for (int l = 0; l < 4; l++) {
								// 중복된다면 다음 방향으로 넘어감
								if (numberingCheck[i][j][l] == number)
									continue LOOP;
								// -1이 검사되었다는 것은 저장된 값들 중 중복되는 값이 없다.
								if (numberingCheck[i][j][l] == -1) {
									numberingCheck[i][j][l] = number;

									answer[i][j] += set[nextY][nextX];
									break;
								}
							}
						}
					}
				}
			}
		}
		for (int i = 0; i < row; i++) {

			for (int j = 0; j < col; j++) {
				sb.append(answer[i][j]%10);
			}
			sb.append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
	}
}

백준 메모리, 시간