BOJ 2234 · 성곽

알고리즘 분류 : DFS  

성을 DFS로 탐색하면서 3가지 값을 구해야 한다. 첫 번째는 성에 있는 방의 개수(A), 두 번째는 가장 큰 방의 넓이(B), 세 번째는 벽 하나를 제거해서 얻을 수 있는 가장 큰 방의 넓이(C)이다.

• 입력으로 주어지는 맵을 DFS로 탐색한다.
• 현재 칸을 (X, Y)라 할 때, check[X][Y]를 숫자 Z로 채운다.
• 다음 칸으로 이동하기 전에 벽으로 막혀있는지 확인한다.
• 벽을 확인하는 방법은 a[X][Y] & (1<<i) 이다. i는 0~3 값이며, 순서대로 서(0), 북(1), 동(2), 남(3)이다.
• 칸을 이동하면서 이동한 칸의 숫자를 세고, DFS가 종료되면 그 값을 반환한다.
• 이 값 중, 가장 큰 값이 정답 A이다.

• 각 방의 넓이를 area 배열에 저장한다.
• 아직 탐색하지 않은 방이 있는지 확인하고, 있다면 다시 DFS 탐색을 시작한다. Z를 1 증가시킨다.
• DFS를 시작한 횟수가 정답 B이다.

• check 배열에는 1부터 B까지 숫자가 저장되어 있다.
• 하나의 방이라면 각 칸은 같은 숫자를 가지므로, 현재 칸과 인접한 상하좌우 칸을 비교해보면서 다른지 확인한다.
• 값이 다르면, 서로 다른 방이 인접한 것이므로, area 배열에 저장한 값을 더한다.
• 위 값 중 가장 큰 값이, 정답 C이다.

---

C++ 소스코드

#include <cstdio>

int n, m, A, B, C;
int a[50][50], check[50][50], area[2500];
const int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

int dfs(int x, int y, int z) {
    check[x][y] = z;
    int res = 1;
    for (int i=0; i<4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if ((a[x][y] & (1<<i)) || check[nx][ny]) continue;
        res += dfs(nx, ny, z);
    }
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (!check[i][j]) {
                A += 1;
                int k = dfs(i, j, A);
                if (B < k) B = k;
                area[A] = k;
            }
        }
    }
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<4; k++) {
                int ni = i+dx[k], nj = j+dy[k];
                if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
                int x = check[i][j], y = check[ni][nj];
                if (x != y) {
                    int sum = area[x]+area[y];
                    if (C < sum) C = sum;
                }
            }
        }
    }
    printf("%d\n%d\n%d\n", A, B, C);
    return 0;
}

---

Python 3 소스코드

dx, dy = (0, -1, 0, 1), (-1, 0, 1, 0)
A, B, C = 0, 0, 0
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
check = [[0]*n for _ in range(m)]
area = [0]*(n*m+1)

def dfs(x, y, z):
    check[x][y] = z
    res = 1
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if not ((a[x][y] & (1<<i)) or check[nx][ny]):
            res += dfs(nx, ny, z)
    return res

for i in range(m):
    for j in range(n):
        if not check[i][j]:
            A += 1
            k = dfs(i, j, A)
            B = max(B, k)
            area[A] = k
for i in range(m):
    for j in range(n):
        for k in range(4):
            ni, nj = i+dx[k], j+dy[k]
            if ni < 0 or ni >= m or nj < 0 or nj >= n:
                continue
            x, y = check[i][j], check[ni][nj]
            if x != y:
                C = max(C, area[x]+area[y])
print("%d\n%d\n%d" % (A, B, C))

---

참고

• 백준 온라인 저지 : BOJ 2234