[백준(Python/Java)] 2234_성곽(DFS, 비트마스킹)

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

2234번: 성곽

 

약간의 비트마스킹을 사용해서 푸는 문제인데, 비트마스킹이 중심인 문제는 아니라고 생각합니다.

단순히 각 방에 위치하는 벽의 정보를 이진수로 바꾸고 남동북서 방향으로 바꿔서 읽어주면 되는 것이죠.

 

예를 들어, 어떤 방의 벽에 대한 값이 11이라면 11을 2진수로 바꾼 뒤 남동북서 방향으로 네 자릿수를 채우면 0111이 됩니다.

즉, 남쪽에 대한 값만 0로 이동가능하고, 동북서에 대한 값은 1로 이동 불가능하다는 뜻입니다.

 

 

한편, 이 문제에서 구해야 하는 값은 아래 세 가지입니다.

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

1, 2번 같은 경우에는 DFS, BFS를 이용해서 풀 수 있는 기본적인 문제입니다. 따라서 이 문제에서 신경써야 할 부분은 바로 "3)번을 어떻게 풀까?"입니다.

 

다양한 풀이 방법이 있겠지만, 저는 "벽 하나를 제거한다 = 인접해있는 서로 다른 방이다"라고 해석했습니다. 따라서 아래 코드를 보면 아시겠지만 각 방(room)의 위치정보를 rooms라는 전체 배열에 저장해두고 room의 한 위치에서 한 칸 이동했을 때 다른 room에 속한다면 벽 하나를 제거하고 최대 방 크기를 갱신해보려고 했습니다.

 

 

하지만 자바로 문제를 풀었을 때는 각 방의 좌표를 ArrayList로 모아두고, 모든 방을 기록해놓는 또 다른 ArrayList를 사용하니 메모리 초과가 발생했습니다.

 

따라서, 애초에 방문 체크용으로만 썼던 visited배열을 각 방의 번호를 기록하는 데 사용하도록 했고 전체적인 DFS를 수행한 뒤 visited배열을 돌면서 1) 방의 개수와 2) 가장 큰 방의 크기를 우선적으로 구했습니다. 이후에 "벽 하나를 제거하여 얻을 수 있는 가장 넓은 방의 크기"같은 경우에는 기본값을 2) 가장 큰 방의 크기로 초기화하고, visited 배열을 통해 인접한 서로 다른 방인지를 확인해주었습니다.

 

말이 어려운 것 같아서, 아래 코드와 주석을 참고하면 도움이 될 것 같습니다.

 

[풀이 - 파이썬]

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def boundChk(x, y, n, m):
    return 0 <= x < n and 0 <= y < m

def bitExpression(k):
    return bin(int(k))[2:].zfill(4)

def dfs(x, y, visited, room):
    room.append((x,y))
    visited[x][y] = True
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        # 바운드 체크, 성곽 체크
        if 0 <= nx < m and 0 <= ny < n and boundary[x][y][i] == '0':
            # 이미 방문하지 않았다면
            if not visited[nx][ny]:
                dfs(nx,ny, visited, room)

n, m = map(int, input().split())

# 각 지점에서 상하좌우에 벽이 있는지를 비트형태로 표현
boundary = [list(map(bitExpression, input().split())) for _ in range(m)]
# 남쪽 = 8, 동쪽 = 4, 북쪽 = 2, 서쪽 = 1
dx, dy = [1,0,-1,0],[0,1,0,-1]

rooms = []
visited = [[False] * n for _ in range(m)]
for i in range(m):
    for j in range(n):
        if not visited[i][j]:
            room = []
            dfs(i,j, visited, room)
            rooms.append(room)     

# 방 크기를 기준으로 오름차순 정렬
rooms = sorted(rooms, key = lambda x : len(x))
numOfRooms = len(rooms) # 방의 개수
maxRoomArea = len(rooms[-1]) # 가장 큰 방
maxRoomAreaByBreakingWall = len(rooms[-1])

# 벽 하나를 뚫었을 때 가장 큰 방의 크기 구하기
for i in range(numOfRooms):
    for j in range(i+1,numOfRooms):
        for x, y in rooms[i]:
            for d in range(4):
                nx, ny = x + dx[d], y + dy[d]
                # 옆 칸에 있으면 방을 합칠 수 있음
                if 0 <= nx < m and 0 <= ny < n and (nx, ny) in rooms[j]:
                            areaTotal = len(rooms[i]) + len(rooms[j])
                            if areaTotal > maxRoomAreaByBreakingWall:
                                maxRoomAreaByBreakingWall = areaTotal
                                break
print(numOfRooms)
print(maxRoomArea)
print(maxRoomAreaByBreakingWall)

 

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B_2234 {
    public static int n, m;
    public static String[][] boundary;
    public static int[] dx = {1,0,-1,0};
    public static int[] dy = {0,1,0,-1};
    public static int[][] visited;

    public static int numOfRooms, maxRoomArea, maxRoomAreaByBreakingWall;

    static class Point{
        int x, y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }


    public static String bitExpression(int number){
        return  String.format("%04d", Integer.parseInt(Integer.toBinaryString(number)));
    }


    public static void dfs(int x, int y, int[][] visited, int numOfRooms){
        // visited에 현재 방 번호를 입력
        visited[x][y] = numOfRooms;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < m && 0 <= ny && ny < n){
                if(boundary[x][y].charAt(i) == '0'){
                    if(visited[nx][ny] == 0){
                        dfs(nx, ny, visited, numOfRooms);
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        // Input 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        boundary = new String[m][n];
        for(int i=0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < n; j++){
                boundary[i][j] = bitExpression(Integer.parseInt(st.nextToken()));
            }
        }

        // DFS를 수행하면서 방의 개수와 각 방의 번호를 기록
        visited = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j=0; j < n; j++){
                if(visited[i][j] == 0){
                    numOfRooms++;
                    dfs(i,j,visited,numOfRooms);
                }
            }
        }

        // 각 방의 크기를 기록하는 roomArea 배열
        int[] roomArea = new int[numOfRooms+1];

        // visited에 기록된 방번호를 읽고, 해당 방번호의 크기를 증가시킨다.
        for(int[] room : visited){
            for(int i : room){
                roomArea[i]++;
            }
        }

        // 가장 큰 방의 크기
        for(int i = 0; i < roomArea.length; i++){
            maxRoomArea = Math.max(maxRoomArea, roomArea[i]);
        }

        // visited에서 서로 인접한 위치의 방 번호가 다르다면, 벽을 깨고 최대값을 갱신
        maxRoomAreaByBreakingWall = maxRoomArea;
        for(int x = 0; x < m; x++){
            for(int y = 0; y < n; y++){
                for(int d = 0; d < 4; d++){
                    int nx = x + dx[d];
                    int ny = y + dy[d];

                    if(0 <= nx && nx < m && 0 <= ny && ny < n){
                        if(visited[x][y] != visited[nx][ny]){
                            maxRoomAreaByBreakingWall = Math.max(maxRoomAreaByBreakingWall, roomArea[visited[x][y]] + roomArea[visited[nx][ny]]);
                        }
                    }
                }
            }
        }
        System.out.println(numOfRooms);
        System.out.println(maxRoomArea);
        System.out.println(maxRoomAreaByBreakingWall);
    }

}