[백준]1926번 그림 c++

https://blog.encrypted.gg/941?category=773649 를 참고하였다.

 

문제

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

1926번: 그림

 

설명

구해야 하는것은 2가지 이다.

1. 그림의 개수

2. 그림중 넓이가 가장 넓은 것의 넓이

 

1. 을 구할땐 큐에서 pop을 몇번 했는지 세어주면 되고

2. 는 이중 for문을 돌려 bfs의 시작점이 될 수 있는지를 체크해주면 된다.

 

 

코드

#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502]; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n, m;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; // 하우상좌 네 방향을 의미
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++)
            cin >> board[i][j];
    int mx = 0; // 그림의 최댓값
    int num = 0; // 그림의 수
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) { // (i, j)를 시작점으로 하고 싶은 상황, 모든칸 검사
            if (board[i][j] == 0 || vis[i][j]) 
                continue; // 해당 칸이 색칠이 안된 부분(0)이거나 이미 (i, j)를 방문했을 경우 넘어감
            // (i,j)는 새로운 그림에 속해있는 시작점
            num++; // 그림의 수 1 증가
            queue<pair<int, int> > Q;
            vis[i][j] = 1; // (i,j)로 BFS를 시작하기 위한 준비
            Q.push({ i,j });
            int area = 0; // 그림의 넓이

            while (!Q.empty()) {
                area++; // 큐에 들어있는 원소를 하나 뺄 때 마다 넓이를 1 증가시킴
                pair<int, int> cur = Q.front(); //검사할곳 cur 로 지정함
                Q.pop();
                for (int dir = 0; dir < 4; dir++) { // 상하좌우 칸을 살펴볼 것이다.
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
                    if (vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
                    vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
                    Q.push({ nx,ny });
                }
            }
            // (i, j)를 시작점으로 하는 BFS가 종료됨
            mx = max(mx, area); // area가 mx보다 클 경우 mx에 area를 대입. 
        }
    }
    cout << num << '\n' << mx;
}

 

테스트케이스 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

인데 이를 그림으로 표현하면 밑에 사진과 같다.

 

사진과 같이 그림 4개가 만들어지고 가장 큰 그림의 넓이는 9임을 알 수 있다.

그림 1은

 

한번 2중 for문 (BFS)이 돌때, 즉 i=0, j=0 일때

(0,0), (0,1), (1,1), (1,2) 가 큐에 한번씩 들어가서 크기가 4인 그림이 찾아진다.

BFS가 돌고나면  vis 배열에 방문 표시도 남게 된다

 

두번째로 BFS가 돌때는 i=0, j=1 일때인데

(0,1)은 이미 방문한 칸이므로 continue 되어 for문 처음으로 돌아가게 된다.

 

세번째로 BFS가 돌때는 i=0, j=2 일때

(0,2)는 파란색이 아닌칸 이므로 j=2 일때와 마찬가지로 continue 되어 for문 처음으로 돌아간다.

 

이런식으로 모든칸을 검사하여 그림의 크기와 제일 큰 그림의 넓이를 찾아낼 수 있다.

제일 큰 그림의 넓이는 그림들의 area 중에 최댓값을 찾으면 된다.