[백준] 16946번 벽 부수고 이동하기4 (자바 풀이)

문제

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

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

 

풀이

처음에는 모든 벽에서 BFS를 돌려 모든 벽마다 갈 수 있는 곳을 세려고 했으나 이렇게 하면 시간초과가 난다 ㅠㅠ

그래서 다른 방법을 생각해냈다. 모든 0의 묶음을 개수로 표시하고, 해당 벽에서 4방향을 조사해서 다른 묶음이라면 0의 개수를 더해주기만 하면 된다. 

 

예를 들어, 아래와 같은 상황이 있다고 하자.

010         1x2
110   ->   xx2    (x는 벽, 숫자는 0의 개수)
111         xxx

즉, bfs를 돌며 0 묶음을 개수로 따로 표시해 놓는 것이다. 물론 0이 1개 뿐이라 1로 표시하면 헷갈릴 수 있으니 따로 표시하는 것이다. 

 

이렇게 0의 개수를 표시해놓고, 모든 벽에서 4방향을 조사하면서 0 묶음이 다르면 값을 더해줘서 출력하면 된다.

0묶음이 다른것을 확인하기 위해 0묶음을 따로 저장한 배열은 (0의 개수, 묶음 번호) 이런 식의 자료구조를 만들어서 해결하였다. 

 

자세한 내용은 아래 코드를 참고하자.

 

코드

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

public class Baekjoon_16946 {
	static int N, M;
	static int arr[][];
	static Point ans[][];
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static boolean visited[][];
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		visited = new boolean[N][M];
		ans = new Point[N][M];
		arr = new int[N][M];
		for(int i=0; i<N; i++) {
			String str = br.readLine();
			for(int j=0; j<M; j++) {
				arr[i][j] = str.charAt(j) -'0';
				ans[i][j] = new Point(0,0);
			}
		}
		
		int num = 2;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(arr[i][j] == 0 && !visited[i][j]) {
					bfs(i,j, num++);
				}
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(arr[i][j] == 1) {
					check(i,j);
				}else {
					sb.append(0);
				}
			}
			sb.append('\n');
		}
		
		System.out.println(sb.toString());
	}
	
	/* 4방향 조사 */
	public static void check(int x, int y) {
		HashSet<Integer> dict = new HashSet<>();
		int cnt = 1;
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || ny <0 || nx >=N || ny >= M) continue;
			/* 0이면서 다른 묶음일 경우에만 더해줌 */
			if(arr[nx][ny] == 0 && !dict.contains(ans[nx][ny].y)) {
				cnt += ans[nx][ny].x;
				dict.add(ans[nx][ny].y);
			}
		}
		
		sb.append(cnt%10);
	}
	
	/* 0을 개수를 찾는 함수 */
	public static void bfs(int x, int y, int num) {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x,y));
		
		/* 0 묶음 좌표 저장할 큐 */
		Queue<Point> temp = new LinkedList<>();
		temp.add(new Point(x,y));
		
		int cnt = 1;	// 0의 개수 count (시작점 포함해서 1)
		visited[x][y] = true;
		
 		while(!q.isEmpty()) {
 			Point cur = q.poll();
 			for(int i=0;i<4; i++) {
 				int nx = cur.x + dx[i];
 				int ny = cur.y + dy[i];
 				
 				if(nx < 0 || ny <0 || nx >=N || ny >=M ) continue;
 				
 				if(!visited[nx][ny] && arr[nx][ny] == 0) {
 					visited[nx][ny] = true;
 					q.add(new Point(nx,ny));
 					temp.add(new Point(nx,ny));
 					cnt++;
 				}
 			}
		}
 		
 		/* 0묶음 개수 표시 */ 
 		while(!temp.isEmpty()) {
 			Point cur = temp.poll();
 			ans[cur.x][cur.y].x = cnt;	// 개수	
 			ans[cur.x][cur.y].y = num;	// 묶음 번호
 		}
 		
	}
	
	public static class Point{
		int x;
		int y;
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
}

 

결과