[백준 1926/C++] 그림

1. 문제

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

1926번: 그림

---

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)
#define X first
#define Y second

using namespace std;

int MAP[505][505];
int vis[505][505];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0 , -1 };
int num, mx;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> MAP[i][j];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (MAP[i][j] == 0 || vis[i][j]) continue;
			num++;
			queue <pair<int, int>> Q;
			int sqr = 0;
			Q.push({ i,j });
			vis[i][j] = 1;
			while (!Q.empty()) {
				sqr++;
				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 (vis[nx][ny] || MAP[nx][ny] == 0) continue;
					Q.push({ nx, ny });
					vis[nx][ny] = 1;
				}
			}
			mx = max(sqr, mx);
		}
	}
	cout << num << '\n' << mx;
}

---

3. 문제 평가 및 해설

코딩테스트 단골 문제인 BFS의 기초 문제이다.

컴퓨터 공학 관련 전공을 한 학생들이라면, 자료구조나 알고리즘에서 BFS를 배웠을 것이다.

나는 '알고리즘 '에서 BFS는 트리 노드에서 노드를 효율적으로 탐색하는 방식으로 배웠다. 하지만 BFS는 너비 우선 탐색이기 때문에, 노드를 효율적으로 찾는 알고리즘에만 사용되지는 않는다. 대표적으로 미로찾기나 Flood fill과 같은 문제에 많이 사용된다. 코딩테스트에서도 노드를 탐색하는 방법(전위순회,후위순회...)보다 BFS와 map을 활용해서 문제를 해결하는 문제를 많이 내는 것 같다. BFS가 까먹었따고 생각할 때, 한번쯤 와서 풀어보면 좋은 문제인 것 같다.

풀이 방법은 정말로 BFS 알고리즘 그 자체이기 때문에, 생략하겠다.