[BaekJoon 1926번] 그림(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

1926번: 그림

 

 

[문제 설명]

 

 

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 

단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 

가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 

그림의 넓이란 그림에 포함된 1의 개수이다.

 

 

[입력]

 

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 

두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

 

 

[출력]

 

 

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

 

[입출력 예]

 

 

예제 입력 1	예제 출력 1
6 5 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1	4 9

 

 

[문제 풀이]

 

BFS 알고리즘의 기본 문제라고 볼 수 있다.

 

문제의 요구 조건은 아래와 같다.

1. 상하좌우로 연결된 그림 크기

2. 도화지에 있는 모든 그림 개수

 

요구조건을 구하기 위해 입출력예1를 가지고 설명해보도록 하겠다.

 

아래 그림은 도화지이며, 파란색은 1을 의미하고 빨간색은 0을 의미한다.

도화지

여기서 그림을 찾으려면 어떻게 해야할까?

2중 for문을 돌면서 bfs를 돌릴 시작점을 찾으면 된다.

 

 

위 부분(점선)에서부터 bfs를 시작하면  크기가 4인 그림을 찾을 수 있고,

bfs를 돌면서 방문한 좌표에 대해 방문 기록도 저장하기 때문에

다음 그림의 시작점을 찾을 때 중복되는 좌표를 방지할 수 있다.

 

그리고 시작점을 찾을 때마다 새로운 그림이라는 뜻이므로 그림의 개수는 시작점을 찾을 때마다 +1 더해주면 된다.

 

그렇다면 크기는 어떻게 구할까?

크기는 while 문 내에서 큐에서 pop하는 횟수가 그림의 크기라고 볼 수 있다.

 

가장 큰 크기를 구할 때는 max 함수를 사용하여 가장 큰 값이 남아있도록 했다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;

int board[501][501];
bool visited[501][501];

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    queue<pair<int, int>> q;
    int picture_cnt = 0;
    int area[1] = { 0, };

    int n; // 세로
    int m; // 가로
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int num;
            cin >> num;
            board[i][j] = num; // 0은 색칠이 안된 부분, 1은 색칠이 된 부분
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if ((board[i][j] != 1) || (visited[i][j] != false)) continue;
            q.push({ i,j });
            visited[i][j] = true;
            ++picture_cnt; // 그림 개수
            int area_cnt = 0;
            while (!q.empty()) {
                pair<int, int> curlocation = q.front();
                q.pop();
                area_cnt += 1;
                for (int k = 0; k < 4; ++k) {
                    int next_x = curlocation.first + dx[k];
                    int next_y = curlocation.second + dy[k];
                    if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m) continue;
                    if (visited[next_x][next_y] || board[next_x][next_y] != 1) continue;
                    visited[next_x][next_y] = true;
                    q.push({ next_x, next_y });
                }
            }
            area[0] = max(area[0], area_cnt);
        }
    }
    cout << picture_cnt << '\n';
    cout << area[0] << '\n';
}