(C++) 백준 1926번 - 그림

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

1926번: 그림

풀이

BFS를 사용하여 풀이하면 되는 문제이다.

그림의 시작점을 찾기 위해 전체적으로 이중 for문으로 스캔하면서 아직 방문하지 않은 시작점을 찾는다.

그 후 BFS를 사용하여 인접 칸들을 순회하면서 그림의 크기를 알아내었다.

#include <iostream>
#include <queue>
#include <utility>
#define X first
#define Y second

using namespace std;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int picn, mx; // picn : 그림의 수, mx : 그림의 최대 크기
int brd[500][500];
int vst[500][500];
queue<pair<int,int>> Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++){ // 배열 입력
        for(int j = 0; j < m; j++){
            int num;
            cin >> num;
            brd[i][j] = num;
        }
    }
    for(int i = 0; i < n; i++){ // 그림의 시작 부분을 찾기 위해 이중 for문 사용
        for(int j = 0; j < m; j++){
            if(brd[i][j] == 1 && vst[i][j] == 0){ // 새로운 그림의 시작
                picn++; // 그림의 수 증가
                Q.emplace(i, j); // 시작점 큐에 추가
                vst[i][j] = 1; // 시작점 방문 표시
            }
            int size = 1; // 그림의 크기
            while(!Q.empty()){ // 그림 순회
                for(int i = 0; i < 4; i++){
                    int x = Q.front().X + dx[i];
                    int y = Q.front().Y + dy[i];
                    if(x >= 0 && x < n && y >= 0 && y < m){ // 유효성 검사
                        if(brd[x][y] == 1 && vst[x][y] == 0){ // 해당 칸의 값이 1이고, 방문한 적도 없다면 해당 칸은 방문해야 함
                            size++; // 칸을 방문할 때마다 해당 그림의 크기가 1씩 커짐
                            Q.emplace(x, y); // 방문할 칸 큐에 저장
                            vst[x][y] = 1; // 방문 표시
                        }
                    }
                }
                Q.pop();
                if(size > mx) mx = size;
            }
        }
    }
    cout << picn << "\n" << mx << "\n";
}

아래는 DFS를 활용한 풀이이다.

반례에 주의해서 로직을 짜는 것이 중요했다.

#include <iostream>
#include <stack>
#include <utility>
#define X first
#define Y second

using namespace std;

int n,m;
int cnt, mx;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int brd[502][502];
int vst[502][502];
stack<pair<int, int> > S;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    cin >> n >> m;

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

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(brd[i][j] == 1 and vst[i][j] != 1){
                cnt++;
                S.push({i,j});
                vst[i][j] = 1;
            }
            int tmp = 1;
            while(!S.empty()){
                auto cur = S.top();
                S.pop();
                for(int k = 0; k < 4; k++){
                    int nx = cur.X + dx[k];
                    int ny = cur.Y + dy[k];
                    if(nx >= n or nx < 0 or ny >= m or ny < 0) continue;
                    if(vst[nx][ny] != 0 or brd[nx][ny] == 0) continue;
                    ++tmp;
                    S.push({nx, ny});
                    vst[nx][ny] = 1;
                }
                mx = max(mx, tmp);
            }
        }
    }
    cout << cnt << "\n";
    cout << mx;
}