BOJ 2234 성곽(The Castle)

 

문제는 다음과 같다

대충 위와 같이 주어진 성곽이 있다. 실선은 벽을, 점선은 벽이 없어 지나다닐 수 있는 공간을 의미한다.

이 때, 

1. 이 성에 있는 방의 수

2. 가장 넓은 방의 넓이

3. 하나의 벽을 제거하여 얻을 수 있는 가장 큰 방의 크기

를 구하는 것이 문제이다.

 

1, 2번은 DFS/BFS를 여러 번 호출하면 되는 기본적인 그래프 탐색 문제이지만, 3번이 이 문제의 문제라 할 수 있겠다.

 

다른 분들의 3번 문제 해결 방법을 살펴보니 주로 실제 벽을 제거하고, BFS을 통해 벽을 하나 제거하여 얻을 수 있는 가장 큰 방의 크기를 구하는데, 2번 문제를 해결하기 위해 각 방들의 넓이는 이미 구해져 있을것이므로, 벽을 하나 하나 허물며 탐색하는것은 조금 낭비처럼 느껴졌다.

 

 

내 해결방법은 다음과 같다.

 

1,2) DFS를 호출해 각 영역에 고유 숫자(1,2,3...)를 부여하고(방문 여부 확인 및 영역표시), 각 영역의 넓이를 구해 벡터에 저장했다.

3) (1차시도)

    1. 위에서 DFS를 호출하는 도중, 진행 방향에 벽이 있으면 일단 탐색 큐에 넣었다.

    2. DFS가 끝난 후 탐색 큐에 들어있는 정점에 인접한 다른 영역들을 인접 리스트로 만들었다.

각 영역의 넓이는 벡터에 들어있고, 연결 상태는 인접 리스트에 있으므로, 각 방의 넓이에 인접한 방의 넓이의 합의 최대값을 찾았다.

 

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second

short wall[50][51], rooms[50][51];
int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; // 서북동남
int n, m, rNum=1, area;

bool bound(int x, int y) {return x>=0&&x<n&&y>=0&&y<m;}

void dfs(int x, int y, queue<pii> &Q) { // 각 방의 넓이 및 고유 번호 표시
    rooms[y][x] = rNum;
    area++;
    if(wall[y][x])
        Q.push({x,y});
    for(int i=0;i<4;++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if(!bound(nx, ny) || rooms[ny][nx] != 0 || wall[y][x] & (1<<i))
        // 범위 벗어나거나 방문된 방이거나 벽을 만나면 패스
            continue;
        
        dfs(nx, ny, Q);
    }
}

int main() {
    cin >> n >> m; // m by n
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j)
            cin >> wall[i][j];
            
    int maxArea=0;
    queue<pii> Q;
    vector<int> areas;
    
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j) {
            if(rooms[i][j]) // 이미 방문(고유번호 표시)했으면 패스
                continue;
            area = 0;
            dfs(j, i, Q);
            areas.push_back(area); // 각 방의 넓이 저장
            maxArea = max(area, maxArea);
            rNum++; // 방의 수
        }

    set<int> S[rNum];
    bool visited[50][51];
    memset(visited, 0, sizeof(visited));

    while(!Q.empty()) { // 벽에 인접한 위치들에 대해
        pii cur = Q.front();
        Q.pop();
        int x = cur.s, y = cur.f;
        visited[y][x] = true;
        for(int i=0;i<4;++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(!bound(nx, ny) || rooms[ny][nx] == rooms[y][x] || visited[ny][nx])
                continue;
            if(wall[y][x] & (1<<i)) { // 벽이 있고, 다른 방이면
                S[rooms[y][x]].insert(rooms[ny][nx]); // 현재 방 번호에 인접한 방의 번호 추가
                S[rooms[ny][nx]].insert(rooms[y][x]);
            }
        }
    }
    
    int bArea = 0;
    
    for(int i=1;i<rNum;++i) { 
        for(int e:S[i]) // i번 방에 인접한 방들에 대해
            if(e != i)
                bArea = max(bArea, areas[i-1]+areas[e-1]);
                // 방을 합쳤을때 최대 넓이 구함
    }
    printf("%d\n%d\n%d", rNum-1, maxArea, bArea);
}

 안타깝게도 오답.. 아마 queue에 정점을 넣을 때 빠지는 정점들이 있는 것 같다.

공식 TC도 넣어봤지만 문제를 모르겠다.

 

3) (2차시도)

    1. 위에서 DFS를 호출하는 도중, 진행 방향에 벽이 있으면 일단 탐색 큐에 넣었다.

    2. DFS가 끝난 후 탐색 큐에 들어있는 모든 정점에 대해 인접한 다른 방이 있으면 이들을 인접 리스트로 만들었다.

탐색 대상 위치를 큐에 넣지 않고. (0,0)부터 (m,n)까지 모든 정점에 대해 인접한 다른 방이 있는지 확인하고, 있으면 인접리스트로 만들었다.

while(!Q.empty()) 대신 2중 for-loop를 이용한게 전부다.

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second

short wall[50][51], rooms[50][51];
int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; // 서북동남
int n, m, rNum=1, area;

bool bound(int x, int y) {return x>=0&&x<n&&y>=0&&y<m;}

void dfs(int x, int y, queue<pii> &Q) {
    rooms[y][x] = rNum;
    area++;
    if(wall[y][x])
        Q.push({x,y});
    for(int i=0;i<4;++i) {
        if(wall[y][x] & (1<<i))
            continue;
        int nx = x + dx[i], ny = y + dy[i];
        if(!bound(nx, ny) || rooms[ny][nx] != 0)
            continue;
        dfs(nx, ny, Q);
    }
}

int main() {
    cin >> n >> m; // m by n
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j)
            cin >> wall[i][j];
            
    int maxArea=0;
    queue<pii> Q;
    vector<int> areas;
    
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j) {
            if(rooms[i][j])
                continue;
            area = 0;
            dfs(j, i, Q);
            areas.push_back(area);
            maxArea = max(area, maxArea);
            rNum++;
        }

    set<int> S[rNum];
    int bArea = 0;
    
    // queue 대신 모든 위치 방문하며 인접한 방 찾기
    for(int y=0;y<m;++y) {
        for(int x=0;x<n;++x) {
            for(int i=0;i<4;++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if(!bound(nx, ny) || rooms[ny][nx] == rooms[y][x])
                    continue;
                if(wall[y][x] & (1<<i)) {
                    S[rooms[y][x]].insert(rooms[ny][nx]);
                    S[rooms[ny][nx]].insert(rooms[y][x]);
                }
            }
        }
    }

    for(int i=1;i<rNum;++i) {
        for(int e:S[i])
            if(e != i)
                bArea = max(bArea, areas[i-1]+areas[e-1]);
    }
    printf("%d\n%d\n%d", rNum-1, maxArea, bArea);
}