[C++] 백준/BOJ - 14925 : 목장 건설하기 ( BFS 풀이 )

문제 이해 단계

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

14925번: 목장 건설하기

MxN 맵에 장애물이 있다. 장애물은 1과 2로 나타난다.

이때 정사각형을 최대한 크게 만들 때,
정사각형 변의 길이 L의 길이를 구하는 문제

 

---

문제 접근 단계

문제는 굉장히 직관적이다.

제한사항부터 바로 살펴보면 N과 M의 최대 길이가 5000인 상황.

5000 x 5000 = 25,000,000까지 가능하다. 
브루트 포스는 힘들어 보인다.

만들어야 하는 것은 2차원 맵이 주어지기도 했고,
브루트포스도 불가능하기에 BFS로 접근해보려고 한다.

그런데 구해야 하는 것이, 가로와 세로가 같은 것을 인식해야 한다. 
그래서 방법을 바꿔보기로 했다.

2차원 맵에서 이동을 통해 만들 수 있는 가장 작은 정사각형은 뭘까?
한 칸짜리를 제외하곤 2x2 정사각형일 것이다.

이게 무슨 소리냐면 아래 그림과 같이 움직이면 2x2 정사각형이 된다.

BFS 탐색으로 해당 패턴으로 움직이면 2x2 정사각형이 만들어진다.

그런데 재밌는 건 이 2x2 정사각형을 겹치면 3x3, 4x4,
다른 모든 길이의 정사각형을 만들 수 있다는 것이다.

위와 같이 겹쳐가면서 만들 수 있다.

---

최적화

위 방식은 계속 겹쳐서 만들고,
모든 행과 열에 대해서 BFS를 실행하는 것이기 때문에 시간이 오래 걸린다.
그래서 필요 없는 반복을 줄이는 최적화를 해야 한다.

해당 문제에서 구하라고 한 것은, 가장 큰 정사각형의 길이 L이라고 했다.

그렇기 때문에 만약 탐색을 하다가
어떤 부분에서 길이가 K인 정사각형이 나왔다면,
더 이상 K이하인 정사각형에 대해서 검사할 필요가 없다.

어차피 길이 K인 정사각형이 나온 순간, 최소 답은 K가 되는 것은 확정됐다.
그렇기에, 다음에 찾아야 할 것은 길이가 K+1인 정사각형이다.

어떤 좌표를 정사각형의 왼쪽 모서리이고,
길이가 K+1이라고 가정한 뒤, 오른쪽과 아래로 좌표를 검사한다.

그 사이에 1과 2가 하나라도 있다면,
그 좌표는 BFS를 돌릴 필요도 없이 K+1인 정사각형이 되지 않는 것이다.

이런 방식으로 최적화를 할 수 있다.
자세한 것은 코드 구현 단계에서 자세하게 다루겠다.

 

---

문제 구현 단계

 // 좌표 구조체 
struct Point{
    int x;
    int y;
};

// 정사각형 만들고 체크 
int bfs(int sx, int sy){
    // 방향 패턴
    int dx[] = {0,1,1};
    int dy[] = {1,1,0};

    int L = 1; // 길이 L
    queue<Point> q;
    bool v[M+1][N+1]; // 방문 체크
    v[sx][sy] = true; // 시작 지점 방문 체크
    memset(v,false,sizeof(v));
    q.push({sx,sy});

    while(!q.empty()){
        int size = q.size(); // 확장시킨 정사각형 크기
        while(size--){
            int x = q.front().x;
            int y = q.front().y;
            q.pop();
            for(int i = 0; i < 3; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 중간에 정해진 좌표에서 나가거나 장애물을 만나면 바로 종료
                if(nx > M || ny > N || 
                map[nx][ny] == 1 || map[nx][ny] == 2) return L;

                // 방문하지 않은 곳만 다시 큐에 담음
                if(!v[nx][ny]){
                    q.push({nx,ny});
                    v[nx][ny] = true;
                }
            }
        }
        L++; // 확장시킨 정사각형이 모두 통과하면(장애물이 하나도 없다면) L+1
    }
    return L;
}

BFS 탐색을 통해 2x2 정사각형을 반복해서 만드는 BFS 함수이다.

매개변수로 시작 좌표를 받는다.
좌표 표시를 편하게 하기 위해 Point라는 구조체를 선언했다.

위에서 언급했던 2x2 정사각형을 만드는 방향 패턴은 dx와 dy 배열이고,
길이 L이 정사각형의 한편 길이에 해당한다.

BFS는 큐를 사용하여 돌리는데, size라는 변수를 둠으로써 확장의 단계를 구분한다.

맨 처음에는 1x1 정사각형이기 때문에
확장이 1번 일어나는 것이 1x1 정사각형의 확장에 해당되고,

다음에는 큐에 3개가 들어있어 size = 3 이기 때문에 
확장이 총 3번 일어나는 것이 2x2 정사각형의 확장에 해당된다.

확장을 하는 와중에 범위에서 벗어나거나,
장애물(1,2)을 만나면 그 즉시 길이 L을 반환하고 BFS를 종료한다.

size의 반복이 끝날 때까지 return 되지 않는다면
정사각형이 형성된 것이므로 L+1을 해줘 길이를 늘여준다.

최종적으로 반환하는 것은 정사각형의 길이 L이다.

/ 해당 좌표가 size 길이의 사각형을 만들 수 있는가 체크
bool checkMap(int x, int y, int size){
    if(x+size > M+1 || y+size > N+1) return false;
    for(int i = x; i < x+size; i++){
        for(int j = y; j < y+size; j++){
            if(map[i][j] == 1 || map[i][j] == 2) return false;
        }
    }
    return true;
}

다음은 최적화를 위해 만든 checkMap 함수이다.
매개변수로 (x, y) 좌표, 그리고 정사각형의 길이 size를 받는다.

일단 if문을 통해 현재 위치에서 길이를 더한 값이 범위를 벗어나면
볼 것도 없이 잘못된 값이므로 false를 반환한다.

그렇지 않다면 일일이 이중반복을 통해 확인해 준다.
모두 통과한 경우에만 BFS검사를 들어가도록 해준다.

핵심적인 코드 설명은 여기까지이고, 나머지 전체코드를 아래에 올리고 끝내겠다.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
int N,M;
int map[1001][1001]= {0,};

// 좌표 구조체 
struct Point{
    int x;
    int y;
};

// 정사각형 만들고 체크 
int bfs(int sx, int sy){
    // 방향 패턴
    int dx[] = {0,1,1};
    int dy[] = {1,1,0};

    int L = 1; // 길이 L
    queue<Point> q;
    bool v[M+1][N+1]; // 방문 체크
    v[sx][sy] = true; // 시작 지점 방문 체크
    memset(v,false,sizeof(v));
    q.push({sx,sy});

    while(!q.empty()){
        int size = q.size(); // 확장시킨 정사각형 크기
        while(size--){
            int x = q.front().x;
            int y = q.front().y;
            q.pop();
            for(int i = 0; i < 3; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 중간에 정해진 좌표에서 나가거나 장애물을 만나면 바로 종료
                if(nx > M || ny > N || 
                map[nx][ny] == 1 || map[nx][ny] == 2) return L;

                // 방문하지 않은 곳만 다시 큐에 담음
                if(!v[nx][ny]){
                    q.push({nx,ny});
                    v[nx][ny] = true;
                }
            }
        }
        L++; // 확장시킨 정사각형이 모두 통과하면(장애물이 하나도 없다면) L+1
    }
    return L;
}

// 해당 좌표가 size 길이의 사각형을 만들 수 있는가 체크
bool checkMap(int x, int y, int size){
    if(x+size > M+1 || y+size > N+1) return false;
    for(int i = x; i < x+size; i++){
        for(int j = y; j < y+size; j++){
            if(map[i][j] == 1 || map[i][j] == 2) return false;
        }
    }
    return true;
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> M >> N;

    int len = 0;

    for(int i = 1; i <= M; i++)
        for(int j = 1; j <= N; j++) cin >> map[i][j];
    
    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            // 최대 길이 len보다 1미터 더 큰거를 만들 수 있어야함
            if(map[i][j] == 0 && checkMap(i,j,len+1)) {
                int val = bfs(i,j);
                len = max(len,val);
            }
        }
    }
    cout << len;
}

 

---

시행착오

난 이 문제가 당연히 BFS인 줄 알았는데,
풀고 보니 태그가 다이내믹 프로그래밍이어서 당황했다.

그래서 인터넷 풀이를 찾아보니 오히려 그 방법이 더 획기적이어서 당황했다.

BFS로 푼 방법은 찾아볼 수가 없어서 내가 블로그 쓰니까 좋긴 한데,
뭔가 꼼수 쓴 거 같아서 좀 그렇네.. 아무튼 이렇게도 풀 수 있다.

푸는 데는 역시 3시간 정도 걸려서 코테에서 나오면 틀렸다고 볼 수 있다.

사실 푸는 거는 1시간 정도밖에 안 걸렸는데, 최적화를 안 해줘서 시간초과 늪에 걸렸다.