[백준 16946] 벽 부수고 이동하기 (java)

문제보러가기

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

이문제는 보자마자 음? BFS 써야지 했다가 바로 시간 초과가 나버린 문제다. BFS의 비용을 최소화하기 위해 그룹핑하는 과정부터 필요하다. 이걸 분리 집합이라고 부른다.

 

 

 

 

 

 

 

문제풀이

-그룹화가 된 배열 정보를 담을 수 있게 group [][] 배열에 0 끼리 묶음 정보를 저장한다.

-여기서 포인트는 BFS를 통해 그룹을 만들 때 이미 만들어진 그룹에 속한 인덱스는 탐색하지 않고 넘기는 것

-벽이 아닌 즉 0인 인덱스는 한 그룹에만 속할 수 있기 때문이다. (서로소 성질:분리 집합으로 다룰 수 있음)

-각각 그룹의 번호를 주어 그룹마다 몇 개의 0을 포함하고 있는지 groupSize Map에 저장한다.

 

->테스트 케이스 2번의 경우 이런 식으로 그룹이 만들어진다.

->또한 Map에는 <그룹번호, 그룹 포함된 0 개수> 즉 <1,2><2,3> 이런 식으로 저장이 된다.

->보면 완벽히 겹치는 그룹이 없이 각각 다른 그룹으로 나눠진 걸 볼 수 있다(분리 집합)

-벽인 경우에만 벽을 포함한 인접한 0의 개수를 세어주는 것이기 때문에 벽인 즉 1인 인덱스만 따진다.

-그룹화해놓은 정보를 이용하여 벽에 직접 맞닿은 그룹만 세어주면 된다.

 

->테스트 케이스의 경우를 살펴보면 맞닿은 곳이 이렇게 3개이다.

->따라서 해당 벽의 이동 가능한 숫자는 1번 그룹+2번 그룹+3번 그룹+자신 이 된다.

->그러므로 다시 BFS를 통한 탐색이 아닌 한 번의 탐색만으로 정보를 가져다가 이용할 수 있다.

 

package baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Ex_16946 {
	static int[][] arr,group;
	static int n;
	static int m;
	static Map<Integer,Integer> groupSize;
	public static void main(String[] args) throws Exception{

		//벽 부수고 이동하기 4 BFS/분리집합
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		arr = new int[n][m];
		group = new int[n][m];
		for(int i=0;i<n;i++) {
			String[] str = br.readLine().split("");
			for(int j=0;j<m;j++){
				arr[i][j]= Integer.parseInt(str[j]);
			}
		}
		
		//각각 그룹마다 다른 key값을 가지게해줌 
		int groupCnt=1;
		groupSize = new HashMap<>(); 
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(arr[i][j]==0 && group[i][j]==0) {
					groupSize.put(groupCnt, bfs(i,j,groupCnt));
					groupCnt++;
				}
			}
		}
		//답을 이중배열로 출력함
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(group[i][j]==0) {
					sb.append(count(i,j)+"");
					continue;
				}
					sb.append(0+"");
			}
			sb.append("\n");
		}
		System.out.println(sb);
		
	}
	//벽에 맞닿은 그룹의 합을 구함
	static int count(int x,int y) {
		int cnt=1;
		if(arr[x][y]==0) return 0;
		Set<Integer> set = new HashSet<>();
		
		//벽에 맞닿은 4방향만 구하면됨
		//그 방향의 그룹의 0의 갯수 정보는 이미 구했기 때문
		for(int i=0;i<4;i++) {
			int[] dx = {0,1,0,-1};
			int[] dy = {1,0,-1,0};
			
			int sx = x+dx[i];
			int sy = y+dy[i];
			
			if(sx < 0 || sy < 0 || sx>=n || sy >= m || group[sx][sy]==0)
				continue;
			//맞닿은 그룹이 중복일 경우를 위해 set에 저장함
			set.add(group[sx][sy]);
			
		}
		for(int size : set) {
			cnt+=groupSize.get(size);
		}
		
		return cnt%10;
	}
	//그룹마다 몇개의 0이 포함되었는지를 리턴해줌
	static int bfs(int x,int y,int groupCnt) {
		int cnt=1;
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x,y));
		group[x][y]=groupCnt;
		while(!q.isEmpty()) {
			Point point = q.poll(); 
			int[] dx = {0,1,0,-1};
			int[] dy = {1,0,-1,0};
			for(int i=0;i<4;i++) {
				int sx = point.x+dx[i];
				int sy = point.y+dy[i];
				
				if(sx < 0 || sy <0 || sx >= n || sy >= m)
					continue;
				//아직 그룹에 속하지 않았고 && 벽이 아니라면 카운트해준다.
				if(group[sx][sy]==0 && arr[sx][sy]==0) {
					group[sx][sy]=groupCnt;
					cnt++;
					q.add(new Point(sx,sy));
				}
			}
		}
		return cnt;
	
	}

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