[백준_16946번] 벽 부수고 이동하기4

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

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

[문제]

 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

 

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

 

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

 

[입력 조건]

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

 

[코드]

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

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

public class BaekJoon_16946 {
	static int[][] map,group;
	static int n,m;
	static HashMap<Integer,Integer> hashmap=new HashMap<>();
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		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];
		group=new int[n][m];
		
		for(int i=0;i<n;i++) {
			String[] str=br.readLine().split("");
			for(int j=0;j<m;j++) {
				map[i][j]=Integer.parseInt(str[j]);
			}
		}
		
		int group_num=1; // 그룹 번호
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j]==0&&group[i][j]==0) {
					// 해쉬맵에 (그룹 번호, 그룹에 속해있는 칸의 갯수)를 저장한다.
					hashmap.put(group_num,make_group(i,j,group_num));
					group_num++;
				}
			}
		}
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				sb.append(break_wall(i,j));
			}
			sb.append('\n');
		}
		
		System.out.println(sb);
	}
	
	// 분리 집합 -> 0으로 이루어진 그룹에 번호를 지정하고, 해당 그룹에 속해있는 칸의 갯수를 count 
	static int make_group(int x, int y, int num) {
		int count=1; // 그룹에 속해있는 칸의 갯수
		Queue<Point_16946> q=new LinkedList<>();
		q.offer(new Point_16946(x,y));
		group[x][y]=num;
		
		while(!q.isEmpty()) {
			Point_16946 p=q.poll();
			
			for(int i=0;i<4;i++) {
				int nx=p.x+dx[i];
				int ny=p.y+dy[i];
				
				if(nx<0||ny<0||nx>=n||ny>=m) continue;
				
				// 벽이 없는 곳이며 아직 그룹에 속해있지 않은 곳 탐색
				if(map[nx][ny]==0&&group[nx][ny]==0) {
					group[nx][ny]=num; // 그룹 번호 부여
					count++; 
					q.offer(new Point_16946(nx,ny));
				}
			}
		}
		
		return count; // 그룹에 속해있는 칸의 개수 return
	}
	
	static int break_wall(int x, int y) {
		int sum=1; // 시작 지점(벽이 있는 곳)도 이동할 수 있는 곳으로 변경하기 때문에 1로 시작
		HashSet<Integer> set=new HashSet<>(); // (x,y)를 기준으로 이동할 수 있는 칸의 그룹 번호가 저장되어 있음
		
		if(map[x][y]==0) // 벽이 없는 곳은 탐색 X
			return 0;
		
		// 벽이 있는 곳을 기준으로 상,하,좌,우 탐색
		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;
			
			// 그룹 번호가 없는 곳은 벽이 있는 곳 -> 이동할 수 없는 칸
			if(group[nx][ny]==0) continue;
			
			// 이동할 수 있는 곳이라면 그룹 번호를 set에 삽입
			if(map[nx][ny]==0)
				set.add(group[nx][ny]);
		}
		
		// set에 삽입된 각 그룹에 속해있는 칸의 개수의 누적합을 구해준다.
		for(int index:set)
			sum+=hashmap.get(index);
		
		return sum%10;
	}
}

 

[고찰]

 처음 문제를 보았을 때는 벽이 있는 칸을 기준으로 BFS 알고리즘을 사용하여 이동할 수 있는 칸의 개수를 count해주는 방식으로 접근했지만 시간 초과를 받았다. 다른 해결방법을 고민해봤지만 쉽게 아이디어가 떠오르지 않아 다른 사람의 포스팅을 참고해 해결하였다. 

 이번 문제를 해결하기 위해서는 분리집합 개념을 사용해야 했다. 우선 벽이 없는(맵의 값이 0인 칸) 칸들의 집합을 그룹 번호를 각각 다르게 해 묶는다. 이후 벽이 있는 곳을 기준으로 상, 하, 좌, 우를 탐색하면서 인접한 곳에 몇개의 그룹과 맞닿아 있는지 탐색해 각 그룹에 속해있는 칸의 개수를 누적한 값을 구해주면 된다. 

 이런 유형의 문제를 처음 접해봐 이런 아이디어를 떠올리는게 쉽지 않았다. 다음에 풀어볼 때는 벽 부수고 이동하기 다른 시리즈 문제도 함께 풀어봐야겠다.