[백준 2234] 성곽 [C]

백준 - 2234

---

풀이

1과, 2의 답은 방 마다 bfs를 사용해 탐색하면 쉽게 구할 수 있다.

3의 답은 방의 각 칸에서 모든 방향으로 벽을 부셔보고 bfs를 사용해 탐색하면 되는데, 매번 방문한 장소를 초기화해주고, 벽을 뚫었다가 탐색이 끝나면 다시 막아주어야 한다.

방향의 순서는 문제에 주어진대로 bit값의 shift연산과 관련이 있으므로 서, 북, 동, 남 순서대로 탐색했다. 

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#include <memory.h>
#define MAX 50
int n, m, graph[MAX][MAX], rear;
bool visited[MAX][MAX];
typedef struct{
    int x, y;
}Point;
Point queue[MAX*MAX], d[4] = {{0,-1}, {-1,0}, {0,1}, {1,0}};
void push(int i, int j){
    queue[rear].x = i;
    queue[rear++].y = j;
}
int bfs(int x, int y){
    int area = 1, front = 0;
    visited[x][y] = 1, rear = 0;
    push(x, y);
	
    while (front != rear){
        x = queue[front].x;
        y = queue[front++].y;
		
        for (int dir = 0, bit = 1; dir < 4; dir++){
            if (!(graph[x][y] & bit)){

                int tx = x + d[dir].x, ty = y + d[dir].y;
                if (tx >= 0 && ty >= 0 && tx < m && ty < n){
                    if (!visited[tx][ty]){
                        visited[tx][ty] = 1;
                        push(tx, ty);
                        area++;
                    }	
                }
            }
            bit <<= 1;
        }
    }
    return area;
}
int main(){
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &graph[i][j]);
			
    int cnt = 0, max_area = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (!visited[i][j]){
                int temp = bfs(i, j);
                max_area < temp && (max_area = temp);
                cnt++;
            }
    printf("%d\n%d\n", cnt, max_area);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            for (int dir = 1; dir <= 8; dir <<= 1)
                if (graph[i][j] & dir){
                    memset(visited, 0, sizeof(visited));
                    graph[i][j] -= dir;
                    int temp = bfs(i, j);
                    max_area < temp && (max_area = temp);
                    graph[i][j] += dir;
                }
    printf("%d", max_area);
}

---

출처

2234번: 성곽