벽 부수고 이동하기 4_16946

• 0을 다센 후에 근접해있는 1에 그 수를 더해주는 방식으로 했다.
• 시간이 간당간당 할 정도로 느리다
• BufferedReader를 사용했다 연습좀 해야겠다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String str = bf.readLine();
		StringTokenizer st = new StringTokenizer(str);
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[N][M];
		
		for(int i = 0;i<N;i++) {
			String s = bf.readLine();
			for(int j = 0;j<M;j++) {
				arr[i][j] = s.charAt(j)-'0';
			}
		}
		
		Queue<Node> q = new LinkedList<Node>();
		Queue<Node> save = new LinkedList<>();
		boolean[][] check = new boolean[N][M];
		
		for(int i = 0;i<N;i++) {
			for(int j = 0;j<M;j++) {
				if(arr[i][j] != 0 || check[i][j])
					continue;
				int cnt = 0;
				q.add(new Node(i,j));
				check[i][j] = true;
				
				while(!q.isEmpty()) {
					cnt++;
					Node node = q.poll();
					
					for(int k = 0;k<4;k++) {
						int nr = node.r + dr[k];
						int nc = node.c + dc[k];
						if(nr< 0|| nr>=N || nc<0 || nc>=M || check[nr][nc])
							continue;
						if(arr[nr][nc] == 0) {
							check[nr][nc] = true;
							q.add(new Node(nr,nc));
						}else {
							save.add(new Node(nr,nc));
							check[nr][nc] = true;
						}
					}
				}
				while(!save.isEmpty()) {
					Node node = save.poll();
					int nr = node.r;
					int nc = node.c;
					arr[nr][nc] += cnt;
					check[nr][nc] = false;
				}
			}
		}
		for(int i = 0;i<N;i++) {
			for(int j = 0;j<M;j++) {
				System.out.print(arr[i][j]%10);
			}System.out.println();
		}
	}
	static class Node{
		int r, c;
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
}

문제

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