[210326][백준/BOJ] 1926번 그림

문제

입출력

---

풀이

BFS를 이용하는 문제이다.
출력값으로 그림의 개수와 가장 큰 그림의 크기를 출력해야 한다.
따라서 BFS의 시작점이 한개가 아니라 여러개인 문제이다.

1. 시작점은 이중 for문을 돌면서 방문한적이 없거나 색칠이 된 부분을 찾으면 된다.
2. 시작점을 찾을때마다 그림의 개수를 추가해준다.
3. 시작점을 찾으면 시작점을 방문했다는 표시를 남기고 큐에 push한 다음에 탐색을 시작하면 된다.
4. 현재 위치는 큐의 front값으로 알 수 있고 현재 위치를 pop하며 현재 위치에서 상하좌우 위치에 접근한다.
5. 상하좌우의 위치가 범위를 벗어나지 않고 방문한적이 없거나 색칠이 된 부분이라면 방문을 하고 push를 한다.
6. 이를 큐가 empty 상태가 될 때 까지 반복한다.

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair의 first second에 편하게 접근하기 위해

int board[502][502]; // 도화지
bool vis[502][502]; // 도화지 방문여부 확인
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 }; // 상하좌우에 접근하기 위해

int main()
{
	int n, m;
	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)
		{
			if (vis[i][j] || board[i][j] == 0) continue; // 방문한적 있거나 색칠 안되어 있으면 continue
			num++; // 아니면 그림의 개수 + 1
			queue<pair<int, int>> Q;
			vis[i][j] = 1; // BFS의 시작점 
			Q.push({ i,j }); // 시작점을 Q에 push
			int area = 0; // 각 그림의 크기 구하기 위해

			while (!Q.empty()) 
			{
				area++; 
				auto cur = Q.front(); // 현재 위치는 Q의 front값
				Q.pop(); // 현재 위치 저장 후 pop
				for (int dir = 0; dir < 4; ++dir) // 상하좌우 검색하기 위해
				{
					int nx = cur.X + dx[dir]; // 현재 위치의 x값에서 상하좌우
					int ny = cur.Y + dy[dir]; // 현재 위치의 y값에서 상하좌우
					if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위를 벗어나면 continue
					if (vis[nx][ny] || board[nx][ny] == 0) continue; // 방문한적 있거나 색칠 안되어 있으면 continue
					vis[nx][ny] = 1; // 방문한 위치에 방문했다는 표시
					Q.push({ nx, ny }); // 방문한 위치값 push
				}
			}
			mx = max(mx, area); // 각 지역중에 최대 크기 지역 구하기 위해
		}
	}
	cout << num << '\n' << mx;
}

---

느낀점

BFS 문제를 처음 풀어보았다.
역시 소문대로 절대 쉽지 않은 문제라는것을 깨달았다.
이론은 대충 알고는 있었지만 구현은 처음 해봤는데 어떠한 느낌으로 구현을 해야하는지는 알 수 있었다.
BFS 문제들의 큰 틀은 다 비슷할거니까 지금 짠 코드를 다시 보면서 어떤 로직으로 이것을 구현했는지 곰곰히 생각해보면서 제대로 이해하도록 노력해야겠다.