[백준] 1012번 유기농 배추 (C++, JAVA)

1012번: 유기농 배추

이차원 배열을 돌면서 값이 1인 곳이 있으면 그걸 시작으로 BFS 해준다.

해당 위치의 상하좌우의 값이 1이면 큐에 그 위치를 넣어놓고

큐가 empty할 때까지 반복해준다.

 

< C++ 코드 >

#include <iostream>
#include <queue>
using namespace std;

int cnt = 0;
void Bfs(int field[][51], int i, int j, int M, int N) {
	queue < pair <int, int> > q;
	q.push(pair<int, int>(i, j));

	field[i][j] = 0; //체크한 상태니까 0으로 바꿔줌

	while (!q.empty()) {
		int x = q.front().first, y = q.front().second;
		if (x - 1 >= 0 && field[x - 1][y] == 1) { //상
			q.push(pair<int, int>(x - 1, y));
			field[x - 1][y] = 0;
		}
		if (x + 1 < M && field[x + 1][y] == 1) { //하
			q.push(pair<int, int>(x + 1, y));
			field[x + 1][y] = 0;
		}
		if (y - 1 >= 0 && field[x][y - 1] == 1) { //좌
			q.push(pair<int, int>(x, y - 1));
			field[x][y - 1] = 0;
		}
		if (y + 1 < N && field[x][y + 1] == 1) { //우
			q.push(pair<int, int>(x, y + 1));
			field[x][y + 1] = 0;
		}
		q.pop();
	}
}

int main() {
	int T;
	cin >> T;

	int M, N, K, X, Y;
	for (int t = 0; t < T; t++) {
		int field[51][51] = { 0 };
		cin >> M >> N >> K;
		for (int k = 0; k < K; k++) {
			cin >> X >> Y;
			field[X][Y] = 1;
		}
		for (int i = 0; i < M; i++)
			for (int j = 0; j < N; j++)
				if (field[i][j] == 1) {
					Bfs(field, i, j, M, N);
					cnt++;
				}
		cout << cnt << "\n";
		cnt = 0;
	}

	return 0;
}

 

< JAVA 코드 >

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_1012_유기농배추 {
	private static int T, M, N, K;
	private static int arr[][], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	private static boolean chk[][];
	private static Queue <int[]> q = new LinkedList<>();
	
	public static void bfs() {
		while(!q.isEmpty()) {
			int X = q.peek()[0], Y = q.poll()[1];
			for(int i = 0; i < 4; i++) {
				int x = X + dx[i], y = Y + dy[i];
				if(x < 0 || x >= N || y < 0 || y >= M || arr[x][y] == 0 || chk[x][y]) continue;
				chk[x][y] = true;
				q.offer(new int[] {x, y});
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);	
		int T = sc.nextInt();
		for(int t = 1; t <= T; t++) {
			M = sc.nextInt(); N = sc.nextInt(); K = sc.nextInt();
			arr = new int[N][M]; chk = new boolean[N][M];
			for(int i = 0; i < K; i++) {
				int y = sc.nextInt(), x = sc.nextInt();
				arr[x][y] = 1;
			}
			int res = 0;
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(chk[i][j] == false && arr[i][j] == 1) {
						q.offer(new int[] {i, j});
						chk[i][j] = true;
						res++;
						bfs();
					}
				}
			}
			System.out.println(res);
		}
	}
}