1926. 그림 (C++)

이번 문제느 BFS를 이용하여 푸는 문제였다.

 

BFS를 사실 학교 다녔을 때 배웠던 기억이 있긴한데, 그게 뭐였는지는 까맣게 잊고 있었다..

그런데 이번에 강의를 통해서 다시금 기억과 구현을 하게 됐고, 그 첫번째 문제로 이 문제를 택했다.

 

이 문제는 BFS 를 사용하는데 있어서 가장 기본적인 문제라고 생각한다.

 

문제에서 보면 그림의 개수 와 그림중 가장 넓이가 넓은 것을 출력하라고 했다. 원하는 수가 두개이다.

 

예제 입력 1을 보고 설명해보자면, 1로 시작하는 그림은 총 4개, 가장 큰 그림은 9의 크기인 우 하단의 그림이 될 것이다. 이걸 어떻게 풀면 될까?

 

BFS를 사용하자!

BFS : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

BFS는 나중에 다른 글로 자세히 설명하겠다.

일단 이중 for문을 돌며 모든 인덱스를 돌기 시작한다. 후에 0이 아니거나 이미 방문한 인덱스가 아닐 경우 먼저 그림이 시작하는 것이니 그림의 개수를 하나 올려주고, BFS로 해당하는 인덱스를 큐에 넣고, 그 인덱스의 상,하,좌,우를 돌며 해당하는 조건이 있는지 살펴보는 방식이다. 

상하좌우를 돌며 이어지는 1을 찾게 되고, 다음으로 넘어갈때마다 그림의 넓이를 하나씩 더해준다. 그렇게 큐가 다 비워질때까지 돌고나면 인덱스의 모든 그림을 파악할 수 있게 된다.

설명을 개같이 못한다. 더 공부하겠다.

 

코드 봅시다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int board[502][502];
bool dist[502][502];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int n,m;

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 cnt = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(board[i][j] == 0 || dist[i][j]) continue;
			cnt++;
			int num = 0;
			queue<pair<int,int>> Q;
			Q.push({i,j});
			dist[i][j] = 1;
			while(!Q.empty()) {
				num++;
				auto cur = Q.front(); Q.pop();
				for(int dir = 0; dir < 4; dir++) {
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
					if(dist[nx][ny] || board[nx][ny] == 0) continue;
					dist[nx][ny] = 1;
					Q.push({nx,ny});
					
				}
			}
			mx = max(mx, num);
		}
	}
	cout << cnt << '\n' <<  mx;
}

board가 0과 1이 쓰여지는 곳

bool 형식인 dist는 board의 인덱스가 지나간 곳인지 아닌지를 판단하는 배열

dx,dy는 그냥 상하좌우 편리하게 사용하려고 만든 배열

 

중간에 cnt와 num 가 각각 그림의 수, 그림의 크기 이다.

그림의 크기는 우리가 파악한 그림들 중에 가장 큰 것을 저장해야 하기 때문에 max함수를 사용했다.(STL 짱)

큐에 인덱스 위치를 넣을 때 pair를 사용하면 편리하다. 많이들 사용하자.

 

이렇게 하면 원하는 답이 나온다!

 

BFS는 어렵지만, 문제 자체는 푸는게 너무 재밌었다. 처음엔 손도 못대겠다가 어떻게 돌아가는지 대충 알게 되니 재미있어진듯 하다. 복습과 다른 문제 풀이를 열심히 하자.