[백준_2234번] 성곽

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

2234번: 성곽

[문제]

 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

 

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다. 성은 m×n(1 ≤ m, n ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

 

[입력 조건]

 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

 

[코드]

import java.util.*;

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

public class BaekJoon_2234 {
	static int n,m,room_count=0,room_area=0,max=0;
	static int[][] map;
	static boolean[][] visited;
	// 서,북,동,남 순으로 탐색해야 함
	static int dx[]={0,-1,0,1};
    static int dy[]={-1,0,1,0};
    
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		m=sc.nextInt();
		n=sc.nextInt();
		map=new int[n][m];
		visited=new boolean[n][m];
		
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				map[i][j]=sc.nextInt();
		
		// 벽을 허물기 전 방의 개수, 가장 넓은 방의 넓이 구하기
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(!visited[i][j]) {
					// bfs가 한번 수행될 때 마다 방의 개수가 count 된다.
					room_area=Math.max(room_area, bfs(i,j));
					room_count++;
				}
			}
		}
		
		System.out.println(room_count);
		System.out.println(room_area);
		
		// 벽 허물기
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				// 비스마스크를 1,2,4,8로 늘려가면서 서,북,동,남 순으로 벽을 허문다.
				for(int bit=1;bit<=8;bit<<=1) {
					/*
					 * 해당 좌표와 비트마스크의 &연산 값이 1이라면 bit 방향에 벽이 있다는 것이기 때문에
					 * 해당 방향의 벽을 허문 상태에서 방의 최대 넓이를 구한 후 다음 경우를 위해 값을 복구한다. 
					 */
					if((map[i][j]&bit)!=0) {
						visited=new boolean[n][m];
						map[i][j]-=bit; // 벽 허물기
						max=Math.max(max, bfs(i,j)); // 최대 방 넓기 구하기
						map[i][j]+=bit; // 벽 복구
					}
				}
			}
		}
		
		System.out.println(max);
	}
	
	static int bfs(int x,int y) {
        // TODO Auto-generated method stub
        Queue<Point_2234> q=new LinkedList<>();
        q.add(new Point_2234(x,y));
        visited[x][y] = true;
        int count=1; // 방의 넚이는 시작 좌표도 세야하기 때문에 1부터 시작
        
        while(!q.isEmpty()) {
        	Point_2234 p=q.poll();
            int bit=1; // 해당 방향으로 벽이 있는지 탐색하기 위한 비트마스크
            
            // 서,북,동,남 순으로 탐색
            for(int d=0;d<4;d++) {
            	/*
            	 * 해당 좌표의 값과 비트마스크를 & 연산하면 
            	 * 서,북,동,남 방향에 벽이 있는지 알 수 있다. 
            	 * 
            	 * 연산 결과가 0이라면 벽이 없는 경우이기 때문에 이동 가능
            	 */
                if((map[p.x][p.y]&bit)==0) {
                    int nx=p.x+dx[d];
                    int ny=p.y+dy[d];
                   
                    // 이동한 좌표가 배열 범위 내에 있으며, 아직 방문하지 않았다면 
                    if(0<=ny&&ny<m&&0<=nx&&nx<n&&!visited[nx][ny]) {
                        count++; // 해당 방의 넓이 count
                        visited[nx][ny]=true; // 방문처리
                        q.add(new Point_2234(nx,ny));
                    }
                }
                bit<<=1; // 비트마스크는 1,2,4,8 로 늘려가며 서,북,동,남에 벽이 있는지 체크
            }
        }
        return count;
    }
}

 

[고찰]

 해당 문제는 BFS 알고리즘과 비트마스크를 이용하여 해결해야 하는 문제였다. 문제를 구조화 하기 전 좌표 값의 의미를 이해하는 것이 중요한 문제였다. 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어지기 때문에 만약 좌표 값이 15라면 서, 북, 동, 남 모두에 벽이 있다는 의미이다. 즉, 좌표 값은 해당 방향에 벽이 있는지 알려주는 값이라는 것이다. 그리고 값의 증가가 2진수의 값 증가와 같기 때문에 비트 마스크를 사용하는 것이 효율적이고, 문제에도 적혀있는 힌트이다. 이후 문제를 구조화해보았다. 

 

*** 1) 비트 연산

 만약 좌표의 값이 15일때, 이를 2진수로 바꾸면 1111이 된다. 자릿 수가 1이면 벽이 있다는 것이고, 0이면 벽이 없다는 것이다. 즉, 각 자릿수는 벽의 유무를 나타낸다. 1111이 값과 차례로 1, 2, 4, 8을 &연산 하게되면 1111의 끝 자릿수가 떨어져 나오게 되는데 이를 통해 어떤 방향에 벽이 있는지 없는지를 알아낼 수 있다. 예를들어 1111과 1을 & 연산 하게 되면 해당 좌표의 서쪽에 벽이 있는지 알 수 있게된다. 결과 값은 1이기 때문에 서쪽에 벽이 있다. 

 

*** 2) BFS 알고리즘

2-1) 방문하지 않은 좌표를 기점으로 BFS 함수를 실행해 해당 방과 이어져있는 모든 방들을 방문처리 하여 방의 개수와, 방의 넓이를 셀 수 있다. 

2-2) BFS 함수가 1번 수행될 때 마다 성 안의 방의 개수가 count 되고, BFS 함수 내에서 탐색하는 좌표의 개수는 해당 방의 칸의 개수, 즉 넓이가 된다.

2-3) 시작 좌표의 서, 북, 동, 남 순으로 해당 방향의 벽이 있는지 확인하고(비트마스크와 & 연산을 사용), 벽이 없고, 배열 범위 내에 있으며, 아직 방문하지 않은 곳이라면 이동한다.

 

*** 3) 벽 허물기

3-1) 벽은 1개만 허물 수 있기 때문에 모든 좌표를 탐색하면서 벽이 있다면 하나씩 제거해본다.

3-2) 해당 좌표에 벽이 있는지의 여부는 비트마스크와 & 연산을 통해 알 수 있기 때문에 서, 북, 동, 남 순으로 벽이 있는지 확인하고, 있다면 제거한다.

3-3) 벽을 제거했다면 최대 방의 개수를 구해 최댓값을 갱신한다. 

 

 이번 문제를 통해 비트마스크를 어떻게 활용하는지 배웠다. 이번에는 문제에 2진수를 활용하라고 힌트를 주어 2진수를 활용해야 한다는 것을 캐치했지만 시험에서는 힌트가 주어지지 않기 때문에 스스로 볼 수 있는 능력을 길러야겠다고 느꼈다.