[JAVA] 백준 16946 : 벽 부수고 이동하기 4

문제

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

 

해결 방법

어떤 방식으로 해결해야 되는지 몰라 다른 블로그를 참고했다.

참고한 블로그는 이 곳이다 -> https://devowen.com/253

 

Flood Fill, 즉 플러드 필 알고리즘을 사용해야 한다고 하는데 위 블로그에 자세히 설명되어있다.

 

문제를 보게되면, 벽과 이동할 수 있는 공간이 존재한다.

벽에 해당하는 부분은 부순다음 해당 칸에서 이동할 수 있는 칸의 개수를 계산해서

벽이었던 1의 해당하는 부분은 해당 칸에서 이동할 수 있는 칸의 개수로,

이동할 수 있는 공간인 0은 그대로 0으로 표시한 배열로 출력하는 문제이다.

 

이 문제에서 플로드 필 알고리즘을 사용하는 방법은 먼저 이동할 수 있는 공간들의 그룹을 만들어 주는 것이다.

 

공간의 그룹은 입력에서 0에 해당하는 부분만 보면 되기 때문에 따로 ArrayList에 moveList로 저장해두어 사용하였다.

코드에서는 findGroups 함수 부분이다.

함수 내부에서는 bfs로 이동 가능한 공간을 하나씩 탐색하며 그룹의 번호를 매겼다.

번호 같은 경우 벽에 해당하는 부분은 1로 그대로 두고, 이동할 수 있는 공간의 그룹의 번호를 2부터 시작해서 메겨주었다.

그리고 해당 공간의 크기를 계산하여 HashMap에 (그룹의 번호, 공간의 크기) 순으로 저장해 두었다.

 

다음으론 벽을 저장해둔 ArrayList인 wallList를 통해 벽을 부수고 이동 가능한 공간의 크기를 파악해야 하는데,

각 벽의 상하좌우에 아까 저장해둔 그룹이 몇 개 존재하는지 확인하고 각 그룹의 크기를 더해주면 된다.

코드에선 getCount 부분이다.

상하좌우를 탐색할 때 같은 그룹의 공간이 겹칠 수 있기 때문에 HashSet을 사용해서 저장하면 중복을 자동으로 제거해주기 때문에 같은 그룹이 두 번 더해지는 일을 막아준다.

 

출력은 StringBuilder를 사용하지 않으면 시간 초과가 나기 때문에 사용해 주었다.

 

 

코드

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.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static boolean[][] visit;
	static int N, M;
	static ArrayList<Node> wallList = new ArrayList<>();
	static ArrayList<Node> moveList = new ArrayList<>();
	static HashMap<Integer, Integer> hashMap = new HashMap<>();
	
	static int[][] newMap;

	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
    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];
        visit = new boolean[N][M];
        
        for (int i = 0; i < N; i++) {
        	String[] temp = br.readLine().split("");
        	for (int j = 0; j < M; j++) {
        		map[i][j] = Integer.parseInt(temp[j]);
        		if (map[i][j] == 1) wallList.add(new Node(i, j));
        		else moveList.add(new Node(i, j));
        	}
        }
        
        findGroups();
        getCount();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < M; j++) {
        		sb.append(newMap[i][j]);
        	}
        	sb.append("\n");
        }
        System.out.println(sb);
    }
    
    static void findGroups() {
    	int idx = 1;
    	
    	for (Node temp : moveList) {
    		int cnt = 1;
    		
    		if (!visit[temp.x][temp.y]) {
    			idx++;
				Queue<Node> q = new LinkedList<>();
				q.offer(new Node(temp.x, temp.y));
				visit[temp.x][temp.y] = true;
				map[temp.x][temp.y] = idx;
				
				while(!q.isEmpty()) {
					Node node = q.poll();
					
					for (int a = 0; a < 4; a++) {
						int newX = node.x + dx[a];
						int newY = node.y + dy[a];
						
						if (newX < 0 || newY < 0 || newX >= N || newY >= M || visit[newX][newY]) continue;
						if (map[newX][newY] == 0) {
							q.offer(new Node(newX, newY));
							visit[newX][newY] = true;
							// 해당 빈 공간을 그룹 번호로 바꿔줌
							map[newX][newY] = idx;
							cnt++;
						}
					}
				}
				// 해당 그룹의 번호와 공간 크기 저장
				hashMap.put(idx, cnt);
			}
    	}
    }
    
    static void getCount() {
    	newMap = new int[N][M];
    	for (Node temp : wallList) {
    		// 중복 방지용 HashSet
    		HashSet<Integer> set = new HashSet<>();
    		for (int i = 0; i < 4; i++) {
    			int newX = temp.x + dx[i];
				int newY = temp.y + dy[i];
				
				// 1, 즉 벽이 아닌 다른 공간 그룹이 존재하는 지 확인
				if (newX < 0 || newY < 0 || newX >= N || newY >= M || map[newX][newY] == 1) continue;
				// 존재하면 해당 그룹 번호 추가
				set.add(map[newX][newY]);
    		}
    		
    		int result = 1;
    		for (int a : set) {
    			result += hashMap.get(a);
    		}
    		newMap[temp.x][temp.y] = result % 10;
    	}
    }
}

class Node {
	int x;
	int y;
	
	Node (int x, int y) {
		this.x = x;
		this.y = y;
	}
}