백준 1012번 C++

백준 1012번 유기농 배추

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

1012번: 유기농 배추

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int arr[51][51];
int vis[51][51];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int bfs(int a,int b, int c) {
	for (int x = 0; x < a; x++) {
		for (int y = 0; y < b; y++) {
			arr[x][y] = 0;
			vis[x][y] = 0;
		}
	}
	for (int x = 0; x < c; x++) {
		int dx, dy;
		cin >> dx >> dy;
		arr[dx][dy] = 1;
	}
	int num = 0;
	queue<pair<int, int>>q;
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			if (arr[i][j] == 0 || vis[i][j])
				continue;
			q.push({ i,j });
			num++;
			vis[i][j] = 1;
			while (!q.empty()) {
				pair<int, int>cur = q.front();
				q.pop();
				for (int x = 0; x < 4; x++) {
					int mx = cur.first + dx[x];
					int my = cur.second + dy[x];
					if (mx < 0 || my < 0 || mx >= a || my >= b)
						continue;
					if (arr[mx][my] == 0 || vis[mx][my])
						continue;
					vis[mx][my] = 1;
					q.push({ mx,my });
				}

			}
		}
	}
	return num;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int x = 0; x < n; x++) {
		int a, b, c;
		cin >> a >> b >> c;
		cout << bfs(a, b, c) << endl;
	}
	
}

문제 해설

bfs를 구현하는 문제이다. 사실 bfs는 거의 정석적인 코드 구현방식이 있기 때문에 정석만 알면 어렵지 않은 문제입니다. 중요한 것은 방문했던 곳을 다시 가지 않기 위한 배열을 만들어주는 것입니다. 이미 방문한 곳이라면 continue를 이용하여 queue가 빌 때까지 계속해서 반복문을 돌려서 이동시키는 것입니다. 시작점이 한 개가 아니기 때문에 for문을 통해서 시작점을 찾아주었고dx, dy배열을 이용하여 배열안에서 이동할 수 있도록 해주었습니다. bfs구현이 궁금하다면 바킹독이라는 유튜버의 강의를 듣는 것을 추천합니다.