[백준 1926번] 그림

---

문제 화면

문제 링크 : https://www.acmicpc.net/problem/1926

문제 풀이

이 문제는 queue 자료구조를 이용하는 BFS의 대표적인 문제이다. 지도를 2차배열에 저장한 후 모든 인덱스를 돌면서 1. 그림이 맞는지, 2. 방문하지 않았는지 확인하면서 떨어진 그림의 개수를 센다. 각 그림을 처음 발견할 경우 queue 자료구조를 이용해 그림의 넓이를 구한다. 이때 핵심은

1. 큐에 넣는 순간 방문표시를 한다.

2. 큐에서 원소를 꺼내어 상하좌우로 인접한 칸에 대해

   1. 유효한 칸(그림)이 맞는지
   2. 방문하지 않은 칸이 맞는지

   를 확인하고 위의 두 조건을 만족하면 큐에 넣고 방문표시를 한다.

3. 큐가 빌 때까지 2번을 반복한다.

모든 칸이 큐에 1번씩 들어가기 때문에 시간 복잡도는 칸의 개수를 N이라고 했을 때 O(N)이 된다. BFS는 어느정도 정형화된 틀이 있고 그 정형화된 틀에서 응용 문제가 자주 나오기 때문에 이 문제는 잘 복습해놓는게 도움이 될 것 같다.

제출 코드

#include <iostream>
#include <queue>

using namespace std;

int map[502][502];
int vis[502][502];

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, num = 0, maxarea = 0;

    cin >> n >> m;

    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < m ; j++) {
            cin >> map[i][j];
        }
    }

    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < m ; j++) {
            if(map[i][j]!=1 || vis[i][j]) continue; // 이미 방문했거나 or 땅이 아닌 경우
			num++;
            queue<pair<int,int>> q;
            q.push({i,j});
            vis[i][j] = 1;
            // 처음 그림 발견
            int area = 0;

            while(!q.empty()) {
                pair<int,int> cur = q.front(); q.pop();
                area++; // 뽑는 순간 넓이 세주기
                for(int k = 0 ; k < 4 ; k++) {
                    int nx = cur.first + dx[k];
                    int ny = cur.second + dy[k];
                    if(nx<0 || nx >= n || ny<0 || ny >=m) continue; // 지도 범위 밖
                    if(vis[nx][ny] || map[nx][ny]!=1) continue; // 이미 방문했거나 or 땅이 아닌 경우 
                    vis[nx][ny] = 1;
                    q.push({nx, ny});
                    
                }
                
            }
            if(area>maxarea) maxarea = area;
        }
    }

    cout << num << "\n";
    cout << maxarea << "\n";

    return 0;

}

결론

BFS는 마스터한다고 생각하고 무조건 많이 풀어봐야 할 것 같다.

출처

• https://blog.encrypted.gg/941?category=773649