[BOJ] 16946. 벽 부수고 이동하기 4 - JAVA

🔗 문제

https://www.acmicpc.net/problem/16946

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

 

🧩 풀이 및 코드

문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS), 깊이우선탐색(DFS) , 분리 집합

 

풀이

문제는 1의 위치를 0으로 변환하고 인접한 그룹의 0의 갯수의 합을 구하는 문제다.

일일이 1일 때 인접한 0의 갯수를 BFS를 이용해 구하면 시간초과가 발생한다. 

분리집합을 통해 해결할 수 있다. 

우선, 분리 집합 개념을 이용해 0으로 이루어진 그룹에 번호를 지정하고 해당 그룹의 갯수를 센다.

그룹 번호	그룹에 속한 0의 갯수
1	2
2	3
3	1
4	1
5	1
6	1

 

그 다음 예를 들어 빨간 동그라미 1를 살펴보자.

예제에 나온 빨간 동그라미의 답은 7이다.

빨간 동그라미 주위의 그룹 1, 2, 3 에 해당하는 0의 갯수 + 1 이다.

따라서, 1 주변의 그룹의 속한 0의 갯수를 모두 더한 후 +1 하면 된다.

단, 같은 그룹으로 둘러싸인 경우가 있으므로 HashSet 을 사용해 중복을 없앴다. 

 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_16946_벽부수고이동하기4 {
	
	static int N, M;
	static Map<Integer, Integer> mp = new HashMap<>();		// 그룹 번호, 그룹에 속한 0의 갯수
	static int[][] group, map;
	
	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_bj_16946.txt"));
		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 s = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}
		
		group = new int[N][M];					// 그룹 번호 저장 배열
		int idx = 1;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0 && group[i][j] == 0) {
					group(i, j, idx++);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				sb.append(count(i, j));
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
		br.close();
	}
	
	static int[] du = {-1, 0, 1, 0};
	static int[] dv = {0, 1, 0, -1};
	
	static int count(int u, int v) {
		if(map[u][v] == 0) return 0;
		Set<Integer> set = new HashSet<>();		// 그룹 번호 중복을 제거하기 위해 set 사용
		
		for(int d=0; d<4; d++) {
			int nu = u + du[d];
			int nv = v + dv[d];
			
			if(nu<0 || nu>=N || nv<0 || nv>=M || group[nu][nv]==0) continue;
			set.add(group[nu][nv]);
		}
		
		int sum = 0;
		for(Integer groupNum : set) {
			sum += mp.get(groupNum);
		}
		sum+=1;
		return sum%10;
	}
	
	
	static void group(int u, int v, int idx) {
		group[u][v] = idx;
		Queue<int[]> que = new ArrayDeque<>();
		que.add(new int[] {u, v});
		
		int cnt = 1;
		while(!que.isEmpty()) {
			int[] now = que.poll();
			
			for(int d=0; d<4; d++) {
				int nu = now[0] + du[d];
				int nv = now[1] + dv[d];
				
				if(nu<0 || nu>=N || nv<0 || nv>=M || map[nu][nv]!=0 || group[nu][nv] != 0) continue;
				group[nu][nv] = idx;
				cnt++;
				que.add(new int[] {nu, nv});
			}
		}
		
		mp.put(idx, cnt);
	}
	
}

 

---

Reference

https://settembre.tistory.com/298

[백준/자바] 16946 벽 부수고 이동하기 4