[C++] 백준 1926번: 그림 (DFS)

1926번: 그림

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

정해진 영역에 그림이 그려져 있을 때, 그림의 개수와 가장 넓은 그림의 크기를 구하여라.

---

시간복잡도 어림하기

DFS 알고리즘

 연결요소(Connected Component)의 수와 크기를 구하는 문제이므로 dfs와 bfs를 사용할 수 있습니다. 두 알고리즘 모두 O(n^2)의 시간복잡도를 가지므로 최대 500 x 500 = 250,000 번의 탐색을 진행합니다. 이는 제한 시간 내에 문제를 해결하기 적절한 수치입니다. 이번 풀이에서는 dfs 알고리즘을 사용하여 문제를 해결하겠습니다.

---

알고리즘 설계하기

 dfs 알고리즘은 보통 다음과 같이 구현합니다.

1. 현재 노드에 대한 방문처리
2. 현재 노드와 연결된 다음 노드 탐색
3. 다음 노드에 방문하지 않았다면 다음 노드 방문

 

 이 문제는 단순히 연결 요소를 찾는 것이 아니라 각 연결 요소의 크기 또한 구해야하므로 dfs의 기본 반환값을 1로 두고, 재귀 호출한 dfs의 값을 기존 반환값에 추가하여 연결 요소의 크기를 반환합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n, m, a[504][504], visited[504][504];
vector<int> v;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0 , -1};
int dfs(int y, int x){
    visited[y][x] = 1;
    int ret = 1;
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if(visited[ny][nx]) continue;
        if(a[ny][nx] == 1) ret += dfs(ny, nx);
    }
    return ret;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cin >> a[i][j];
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 0 || visited[i][j]) continue; //그림이 아니거나 이미 방문한 경우
            v.push_back(dfs(i, j));
        }
    }
    sort(v.begin(), v.end()); //그림 크기 오름차순 정렬
    if(v.size() == 0) cout << 0 << '\n' << 0; //그림이 없는 경우
    else
        cout << v.size() << '\n' << v[v.size() - 1]; //그림의 수와 가장 넓은 그림 크기 출력
    return 0;
}

 main 함수에서 입력을 받고 루프를 돌면서 그림의 위치를 찾습니다. 현재 그림이 아직 방문하지 않았다면 현재 위치를 기준으로 dfs함수를 실행합니다.

 

 dfs 함수에서는 연결요소를 모두 탐색하고, 탐색 횟수를 반환합니다. dfs 탐색이 끝나면 그 결과를 vector에 담아, 다음 그림 위치를 탐색합니다.

 

 모든 그림 탐색이 끝나면 vector를 정렬하고, 그림의 수(vector의 크기)와 그림의 최대 크기를 구합니다.

---