boj 2234 성곽

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

2234번: 성곽

저는 두 번의 bfs를 사용하였습니다.

한번은 각 방의 넘버링을 위한 bfs, 다른 한번은 각 방에 인접한 방을 찾기 위한 bfs입니다.

 

최종으로 구해야 할 것이

1. 이 성에 있는 방의 개수

2. 가장 넓은 방의 넓이

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

이렇게 됩니다.

저는 1, 2번은 각 방의 넘버링으로 해결하였고, 3번은 각 방에 인접한 방을 찾아서 해결하였습니다.

 

 

이 문제에서 입력으로 주어지는 숫자는 벽에 대한 정보입니다.

서쪽에 벽이 있으면 1, 북쪽에 벽이 있으면 2, 동쪽에 벽이 있으면 4, 남쪽에 벽이 있으면 8을 더한 값이 주어집니다.

만약에 벽이 없으면 하나도 더해지지 않은 0이 주어질 것이고, 사방에 모두 벽이 있으면 1 + 2 + 4 + 8 = 15가 주어질 것입니다.

 

1, 2, 4, 8을 더한 값이 주어지기 때문에 먼저 비트마스킹을 떠올렸습니다.

벽을 체크하기 위해 wall 배열에 해당 방향에 대한 값을 넣었고,

해당 방향을 체크할 때 해당하는 값인 wall[i]과 list[x][y]를 비교하여

list[x][y] & wall[i]이 0이면 벽이 없는 것이고, 0이 아니면 벽이 있는 것이라고 보시면 되겠습니다.

 

bfs & 비트마스킹으로 각 방에 넘버링을 하였고, 넘버링을 하면서 방의 크기도 같이 구하였습니다.

그 다음 bfs를 한번 더 돌려서 인접한 방 번호를 sideroom에 넣었고 방의 크기 + 인접한 방의 크기를 비교하여 최댓값을 출력하였습니다.

(sideroom을 set으로 한 이유는 중복체크를 하기 위함입니다.)

 

 

[C++]

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
 
set<int> sideroom[2501];
int N, M, wall[4] = { 4, 8, 1, 2 };
int list[50][50], direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
int roomnum, maxroomsize, Room[50][50], Roomsize[2501];
bool visit[50][50];
 
void sidechk(int sx, int sy, int num) {
    queue<pair<int, int> > q;
    q.push({ sx, sy });
    visit[sx][sy] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (Room[nx][ny] != num) {
                sideroom[num].insert(Room[nx][ny]);
                continue;
            }
            if (visit[nx][ny]) continue;
 
            q.push({ nx, ny });
            visit[nx][ny] = true;
        }
    }
}
 
void bfs(int sx, int sy, int num) {
    queue<pair<int, int> > q;
    q.push({ sx, sy });
    visit[sx][sy] = true;
    for (int t = 1; ; t++) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        Room[x][y] = num;
 
        for (int i = 0; i < 4; i++) {
            if (wall[i] & list[x][y]) continue;
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (visit[nx][ny]) continue;
            q.push({ nx, ny });
            visit[nx][ny] = true;
        }
 
        if (q.empty()) {
            Roomsize[num] = t;
            maxroomsize = max(maxroomsize, t);
            break;
        }
    }
}
 
void solve() {
    int maxroomsum = 0;
    cout << roomnum << '\n' << maxroomsize << '\n';
    for (int i = 1; i <= roomnum; i++) {
        set<int>:: iterator iter;
        for (iter = sideroom[i].begin(); iter != sideroom[i].end(); iter++) {
            int s = *iter;
 
            maxroomsum = max(maxroomsum, Roomsize[i] + Roomsize[s]);
        }
    }
 
    cout << maxroomsum << '\n';
}
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visit[i][j]) continue;
            bfs(i, j, ++roomnum);
        }
    }
    memset(visit, false, sizeof(visit));
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visit[i][j]) continue;
            sidechk(i, j, Room[i][j]);
        }
    }
}
 
void input() {
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
    solve();
 
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[51][51];
    static int div[][] = new int[51][51];
    static boolean visit[][] = new boolean[51][51];
    static ArrayList<Integer> roomarea = new ArrayList<>();
    static Set<Integer> s[];
    static int wall[] = { 4, 8, 1, 2 };
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, roomcnt, maxarea, cnt, ans;
 
    static void sidechk(int sx, int sy) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { sx, sy });
        visit[sx][sy] = true;
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny])
                    continue;
 
                if (div[x][y] != div[nx][ny])
                    s[div[x][y]].add(div[nx][ny]);
                else {
                    dq.add(new int[] { nx, ny });
                    visit[nx][ny] = true;
                }
            }
        }
    }
 
    static void solveroom(int sx, int sy) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { sx, sy });
        visit[sx][sy] = true;
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
            div[x][y] = roomcnt;
            cnt++;
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny] || (wall[i] & list[x][y]) > 0)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void func() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j])
                    continue;
                solveroom(i, j);
                roomarea.add(cnt);
                roomcnt++;
                maxarea = Math.max(maxarea, cnt);
                cnt = 0;
            }
        }
 
        s = new HashSet[roomcnt];
        for (int i = 0; i < roomcnt; i++)
            s[i] = new HashSet<>();
 
        for (int i = 0; i < N; i++)
            Arrays.fill(visit[i], false);
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j])
                    continue;
 
                sidechk(i, j);
            }
        }
    }
 
    static void solve() {
        for (int i = 0; i < roomcnt; i++) {
            Iterator<Integer> iter = s[i].iterator();
            while (iter.hasNext()) {
                ans = Math.max(ans, roomarea.get(i) + roomarea.get(iter.next()));
            }
        }
 
        System.out.println(roomcnt + "\n" + maxarea + "\n" + ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        solve();
    }
}