[C++] 1926번 : 그림

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

1926번: 그림

풀이

드디어 자료구조를 넘어 Theme.BFS에 진입했다.

이산수학과 자료구조에서 지겹도록 배운 BFS,DFS인데 막상 코드로 짜려니 신경써줘야 할 것이 많았다.

이 문제는 BFS의 기본문제라고 할 수 있겠다.

Flood Fill이라는 idea를 채용한다고 할 수 있겠는데 Flood Fill이란

예를 들어 그림판에서 내가 양동이 아이콘을 클릭하여 어떤 도형 안쪽을 클릭하면 가득 채워짐을 알 수 있다.

그런데 컴퓨터는 어느 범위까지 채워야하는 지 어떻게 알까? 경계까지 탐색을 통해 알 수 있다.

Flood Fill 설명

이것을 Flood Fill이라고 칭한다. (출처 : 바킹독https://blog.encrypted.gg/941)

[실전 알고리즘] 0x09강 - BFS

아무튼, 2D Array를 이용한 BFS의 가장 기본적인 문제로 어떻게 풀 지 떠올릴지는 어렵지 않을 것이다.

하지만 구현이 어렵다..! (Idea는 떠오르는데 구현을 못한다니 난 정말 전공자인가.)

이 문제와 같이 코드로 덤비다가 머리가 복잡해졌었는데 수도 코드를 작성해보니 금방 풀었다. 물론 참고해서

 

내 코드

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, cnt = 0, val = 0;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!board[i][j] || vis[i][j]) continue;
			cnt++;
			queue<pair<int, int>> q;
			q.push(make_pair(i, j));
			vis[i][j] = 1;
			int temp = 0;
			while (!q.empty()) {
				temp++;
				pair<int, int> 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 (vis[nx][ny] || !board[nx][ny]) continue;
					vis[nx][ny] = 1;
					q.push(make_pair(nx, ny));
				}
			}
			val = max(temp, val);
		}
	}
	cout << cnt << '\n' << val;

}

아 pair을 이용하는 것은 이전 stack 문제에서 사용했던 idea이다. 

https://developer-dz.tistory.com/81

[C++] 2493번 : 탑

당연히 처음이라 어려운 것이겠지.?  이 코드 형태는 정말 웰 노운 형태라고 하니 정진하자