[백준 2234번] 성곽 (Java, C++)

[백준 2234번 성곽 URL]

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

[유사문제]

2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 2667번] 단지번호붙이기

문제에서 요구한 정답은 총 3가지 입니다.

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

여기서 1번, 2번 답은 bfs 메소드를 통해 구할 수 있습니다.

---

1) 2차원 배열 map을 순차탐색하면서 visited[row][col] == false 일 경우, 아직 방문하지 않았다는 뜻이므로

   bfs(row, col) 메소드를 호출합니다. bfs를 호출할 때 마다 roomCnt 변수를 1씩 증가시켜줍니다.

   roomCnt는 방의 갯수를 뜻합니다.

---

2) bfs 메소드에서는 Queue를 이용해서 bfs 탐색을 진행합니다. Queue에서 Node하나를 꺼내는 행위가 방의 크기

를 count하는 것과 마찬가지이므로 q.poll()을 할때마다 roomSize 를 1씩 증가시킵니다.

---

3) bfs 메소드에서 받았던 매개변수부터 시작된 탐색이 모두 끝났을 경우 현재 방의 사이즈와 이전 방의 

최대사이즈인 maxSize 을 비교하여 갱신합니다.

문제에서 요구한 정답은 총 3가지 입니다.

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

여기서 3번 답을 구하기 위해서는 벽을 하나씩 허물고 bfs탐색을 실행해야 합니다.

벽은 동서남북 4방향으로 있기 때문에 bfs탐색을 시작하는 위치에서 4방향에 벽이 있는지 검사한 후, 벽이 있다면 벽을 허물고 bfs 탐색을 시작합니다.

벽을 허무는 breakWall 메소드를 살펴보겠습니다.

반복문이 순차적으로 돌면서 현재 칸의 값 (map[row][col])과 &(AND) 연산을 하고 있습니다.

AND 연산의 결과 값이 0이 아닌 경우에는 그 칸에 벽이 있다는 뜻이므로 map[row][col] 에서 

해당하는 값 ( 1<< i )을 빼준 후에 bfs탐색을 시작합니다. 

해당 칸에서 bfs 탐색이 모두 끝났다면 벽을 하나만 허문다고 했기 때문에 위에서 뺏던 값을 다시 더해줍니다. 

(허문 벽을 원상복구 시킴)

i	1 << i / (bit) - (방향)	map[startRow][startCol]	map[startRow][startCol] & (1 << i)
0	1 / (0001) - (서)	11 (1011)	1
1	2 / (0010) - (북)	11 (1011)	1
2	4 / (0100) - (동)	11 (1011)	0
3	8 / (1000) - (남)	11 (1011)	1

public static void breakWall(int startRow, int startCol) {
        for (int i = 0; i < 4; i++) {
            if ((map[startRow][startCol] & (1 << i)) != 0) {
                for (int j = 0; j < visited.length; j++)
                    Arrays.fill(visited[j], false);
                map[startRow][startCol] -= (1 << i);
                bfs(startRow, startCol);
                map[startRow][startCol] += (1 << i);
            }
        }
    }

---

[자바 소스코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] dirX = { 0, -1, 0, 1 };
    public static int[] dirY = { -1, 0, 1, 0 };
    public static int[][] map;
    public static boolean[][] visited;
    public static int N, M, maxSize = Integer.MIN_VALUE;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        visited = new boolean[M][N];
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        int roomCnt = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs(i, j);
                    roomCnt += 1;
                }
            }
        }
        System.out.println(roomCnt);
        System.out.println(maxSize);
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                breakWall(i, j);
            }
        }
        System.out.println(maxSize);
    }
 
    public static void breakWall(int startRow, int startCol) {
 
        for (int i = 0; i < 4; i++) {
            if ((map[startRow][startCol] & (1 << i)) != 0) {
                for (int j = 0; j < visited.length; j++)
                    Arrays.fill(visited[j], false);
                map[startRow][startCol] -= (1 << i);
                bfs(startRow, startCol);
                map[startRow][startCol] += (1 << i);
            }
        }
    }
 
    public static void bfs(int startRow, int startCol) {
 
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(startRow, startCol));
        visited[startRow][startCol] = true;
        int roomSize = 0;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int wall = map[row][col];
            roomSize += 1;
 
            for (int i = 0; i < 4; i++) {
 
                if ((wall & (1 << i)) > 0)
                    continue;
 
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.offer(new Node(nr, nc));
                }
            }
        }
        maxSize = Math.max(maxSize, roomSize);
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < M) && (col >= 0 && col < N);
    }
 
}
 
class Node {
 
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}
 

---

[C++ 소스코드]

#include <iostream>
#include <queue>
#include <cstring> 
 
using namespace std;
 
#define MAX 50
 
int dir[4][2] = {
    { 0, -1 },{ -1, 0 },{ 0, 1 },{ 1, 0 } // 서 북 동 남
 
};
int map[MAX][MAX];
bool visited[MAX][MAX];
 
int n, m, roomCnt = 0, maxArea = -123123;
 
bool boundary(int row, int col) {
    return (row >= 0 && row < m) && (col >= 0 && col < n);
}
 
void bfs(int row, int col) {
 
    if (visited[row][col])
        return;
 
    int cnt = 0;
    queue<pair<int, int> > q;
    q.push(make_pair(row, col));
    visited[row][col] = true;
 
    while (!q.empty()) {
 
        pair<int, int> p = q.front();
        q.pop();
        int cX = p.first;
        int cY = p.second;
        cnt++;
 
        for (int i = 0; i < 4; i++) {
 
            if ( ((1 << i) & map[cX][cY]) == 0) {
 
                int nX = cX + dir[i][0];
                int nY = cY + dir[i][1];
 
                if (!visited[nX][nY] && boundary(nX, nY)) {
                    visited[nX][nY] = true;
                    q.push(make_pair(nX, nY));
 
                }
            }
 
        }
    }
    roomCnt++;
    if (maxArea < cnt)
        maxArea = cnt;
}
 
void tearDown(int row, int col) {
 
    for (int i = 0; i < 4; i++) {
 
        if ((map[row][col] & (1 << i)) != 0) {
 
            memset(visited, false, sizeof(visited));
            map[row][col] = map[row][col] - (1 << i);
            bfs(row, col);
            map[row][col] = map[row][col] + (1 << i);
 
        }
 
    }
}
 
int main(void) {
 
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            bfs(i, j);
        }
    }
 
 
    cout << roomCnt << endl;
    cout << maxArea << endl;
 
    maxArea = -123123;
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            tearDown(i, j);
        }
    }
 
    cout << maxArea << endl;
 
 
    return 0;
}