[알고리즘] Java / 백준 / 벽 부수고 이동하기 4 / 16946

[알고리즘] Java / 백준 / 벽 부수고 이동하기 4 / 16946

문제

문제 링크

접근 방식

1. 0이 이어져있는 부분들을 각 구역으로 설정하고 구역 번호화 해당 구역의 0 개수를 key와 value로 하는 section이라는 HashMap에 구역 정보를 저장한다.
2. 기존 map 외에 0의 구역들을 표시할 이차원 배열을 생성하고 각 0이 해당하는 구역의 번호를 저장한다.

//map
1100
0011
1100

// zeroMap  0의 각 구역번호를 가짐
0011
2200
0033

1. map에서 각 벽돌을 사방탐색하여 0의 구역들을 중복없이 zeroMap에서 가져오고, 해당 구역들의 0 개수를 모두 합하여 map에 더한다.

코드

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

public class Main_16946 {

	// map에서 이어져있는 0들을 각각 구역 번호로 저장
	// 해당 구역 번호화 그 구역의 0 개수를 key와 value로 section에 저장한다.
	public static void fill(int r, int c, int sectionNum) {
		Queue<int[]> queue = new LinkedList<>();
		List<int[]> blanks = new ArrayList<>(); 
		int blank = 1;
		queue.offer(new int[] {r,c});
		visited[r][c] = true;
		blanks.add(new int[] {r,c});
		while(!queue.isEmpty()) {
			int[] node = queue.poll();
			
			for(int i=0;i<4;i++) {
				int nR = node[0] + dr[i];
				int nC = node[1] + dc[i];
				if(nR<0||nR>=N||nC<0||nC>=M||visited[nR][nC]||map[nR][nC] != 0) continue;
				visited[nR][nC] = true;
				blank++;
				blanks.add(new int[] {nR,nC});
				queue.offer(new int[] {nR,nC});
			}
		}
		section.put(sectionNum, blank);
		for(int i=0;i<blanks.size();i++) {
			int[] node = blanks.get(i);
			zeroMap[node[0]][node[1]] = sectionNum;
		}
		
	}
	
	public static void destroy(int r, int c) {
		
		int block = 1; // 벽을 zero로
		HashSet<Integer> sectionNums = new HashSet<>();
		for(int i=0;i<4;i++) {
			int nR = r + dr[i];
			int nC = c + dc[i];
			
			// 범위를 벗어났거나 벽인 경우 패스
			if(nR<0||nR>=N||nC<0||nC>=M||zeroMap[nR][nC] == 0) continue;
			// 4방향의 구역번호를 중복없이 저장
			sectionNums.add(zeroMap[nR][nC]);
		}
		
		// 현재 벽에서 네 방향으로 zero 구역을 찾고, 해당 구역의 zero수를 모두 더함
		for(int sectionNum : sectionNums) {
			block +=section.get(sectionNum);
		}
		
		
		map[r][c] = block % 10;
	}
	
	static int N,M;
	static int[][] map;
	static int[][] zeroMap;
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	static boolean[][] visited;
	static HashMap<Integer, Integer> section;
	public static void main(String[] args) throws IOException{
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=  new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		
		for(int i=0;i<N;i++) {
			String line = br.readLine();
			for(int j=0;j<M;j++) {
				map[i][j] = line.charAt(j)-'0';
			}
		}
		
		
		// 빈칸인 섹션을 구분하고 zeroMap에는 각 빈칸에 섹션 번호를 넣음
		// 섹션 번호는 Map 구조인 section으로 해당 섹션의 빈칸 수를 알 수 있음
		zeroMap = new int[N][M];
		visited = new boolean[N][M];
		section = new HashMap<>();
		int sectionNum = 1; // sectionNum은 zeroMap에서 구역의 번호로 참조할 건데 벽인 경우를 0으로 하기 위해
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j] == 0 && !visited[i][j]) fill(i,j,sectionNum++);
			}
		}
		
		// 각 벽에 대해 네 방향의 구역을 찾아 해당 구역의 0 개수 합을 벽에 저장
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j] == 1) destroy(i,j);
			}
		}
		
		// 출력
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				sb.append(map[i][j]);
			}
			sb.append("\n");
		}
		
		System.out.print(sb);
	}
	
	

}