1.문제

2.코드

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

public class Main{
	static int[][] map,map2;
	static int N,M,number;
	static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        //세로 가로
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        //구역 표시할 2차원 배열
        map2 = new int[N][M];
        for(int i=0; i<N; i++) {
        	String str = br.readLine();
        	for(int j=0; j<M; j++) {
        		map[i][j] = str.charAt(j)-'0';
        		
        		if(map[i][j] == 1) map[i][j] = -1;
        	}
        }
        //방문 배열
        visited = new boolean[N][M];
        number = 0;
        //갈수있는 구역 갯수 표시
        for(int i=0; i<N; i++) {
        	for(int j=0; j<M; j++) {
        		if(map[i][j] == 0 && !visited[i][j]) {
        			number++;
        			visited[i][j] = true;
        			map[i][j] = able(i,j);
        		}
        	}
        }
        
        visited = new boolean[N][M];
        for(int i=0; i<N; i++) {
        	for(int j=0; j<M; j++) {
        		if(map[i][j] >= 0 && !visited[i][j]) {
        			dfs(i,j,map[i][j]);
        		}
        	}
        }
        
        int[][] result = new int[N][M];
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++) {
        	for(int j=0; j<M; j++) {
        		if(map[i][j] == -1) {
        			//이미 합친 구역인지 확인할 배열
        			int[] check = new int[4];
        	    	for(int k=0; k<4; k++) {
        	    		int new_y = i + move_y[k];
        	    		int new_x = j + move_x[k];
        	    		
        	    		if(new_y<0 || new_y>=N || new_x<0 || new_x>=M || map2[new_y][new_x]==0) continue;
        	    		//넣을수 있는지?
        	    		boolean pos = true;
        	    		
        	    		for(int l=0; l<4; l++) {
        	    			if(check[l] == map2[new_y][new_x]) {
        	    				pos = false;
        	    				break;
        	    			}
        	    		}
        	    		
        	    		if(pos) {
        	    			result[i][j] += map[new_y][new_x];
        	    			check[k] = map2[new_y][new_x];
        	    		}
        	    	}
        	    	
        	    	sb.append((result[i][j]+1)%10);
        		}else {
        			sb.append(0);
        		}
        	}
        	sb.append("\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    
    static int[] move_y = {-1,0,1,0};
    static int[] move_x = {0,-1,0,1};
    public static int able(int y, int x) {
    	
    	int result = 1;
    	
    	for(int i=0; i<4; i++) {
    		int new_y = y + move_y[i];
    		int new_x = x + move_x[i];
    		
    		if(new_y<0 || new_y>=N || new_x<0 || new_x>=M || visited[new_y][new_x]) continue;
    		
    		if(map[new_y][new_x]==0) {
    			visited[new_y][new_x] = true;
    			result += able(new_y,new_x);
    		}
    	}
    	//구역 번호
    	map2[y][x] = number; 
    	
    	return result;
    }
    
    public static void dfs(int y, int x, int num) {
    	visited[y][x] = true;
    	map[y][x] = num;
    	
    	for(int i=0; i<4; i++) {
    		int new_y = y + move_y[i];
    		int new_x = x + move_x[i];
    		
    		if(new_y<0 || new_y>=N || new_x<0 || new_x>=M || visited[new_y][new_x]) continue;
    		
    		if(map[new_y][new_x]==0) {
    			visited[new_y][new_x] = true;
    			dfs(new_y,new_x,num);
    		}
    	}
    }
    
}

3.Review

일반적인 BFS로 풀려고 시도하였으나 시간초과가 나왔다.

그래서 BFS로 빈 공간의 구역을 나눠주고, 그 구역에 해당하는 곳을 다시 갈수있는 수로 다시 채워 주었다.

그리고 벽을 부순 뒤 상하좌우에서 겹치지 않는 곳만 더해주었다.

출력시 (값+1)%10을 해서 출력을 해주었는데 어째서인지 StringBuilder를 사용하면 정답이 되는데, 그냥 문자열로 출력을 하면 오답이 나왔다.

이유를 모르겠다....