Boj 1012 유기농 배추

문제 링크 : 백준 https://www.acmicpc.net/problem/1012

DFS Ver.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int map[][];
	static int T, R, C, baechu;
	static int answer;
	static boolean visited[][];
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };

	public static void main(String[] args) throws NumberFormatException, IOException {

		T = Integer.parseInt(br.readLine());


		for (int tc = 0; tc < T; tc++) {
			answer=0;
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			baechu = Integer.parseInt(st.nextToken());
			map = new int[R + 1][C + 1];
			visited = new boolean[R + 1][C + 1];
			for (int i = 0; i < baechu; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				map[a][b] = 1;
			}

			for (int r = 0; r < R; r++) {
				for (int c = 0; c < C; c++) {
					if (map[r][c] == 1 && !visited[r][c]) {

						dfs(r, c);
						answer++;
					}
				}
			}

			System.out.println(answer);
		}
	}

	private static void dfs(int x, int y) {
		visited[x][y] = true;

		for (int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];

			if (cx >= 0 && cx < R && cy >= 0 && cy < C) {
				if (map[cx][cy] == 1 && !visited[cx][cy]) {
					dfs(cx, cy);
				}
			}
		}
	}
}

BFS Ver.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int map[][];
	static int T, M, N, baechu;
	static int answer;
	static boolean visited[][];
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };

	public static void main(String[] args) throws NumberFormatException, IOException {

		// 테케
		T = Integer.parseInt(br.readLine());

		for (int tc = 0; tc < T; tc++) {
			answer = 0;
			st = new StringTokenizer(br.readLine());

			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			baechu = Integer.parseInt(st.nextToken());
			map = new int[M + 1][N + 1];
			visited = new boolean[M + 1][N + 1];
			// 배추 위치 입력
			for (int i = 0; i < baechu; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				map[a][b] = 1;
//				map[b][a] = 1;
			}

			for (int r = 0; r < M; r++) {
				for (int c = 0; c < N; c++) {
					if (map[r][c] == 1 && !visited[r][c]) {
						bfs(r, c);
						answer++;
					}
				}
			}

			System.out.println(answer);
		}
	}

	private static void bfs(int x, int y) {

		Queue<DOT> queue = new LinkedList<DOT>();
		visited[x][y] = true;
		queue.add(new DOT(x, y));

		while (!queue.isEmpty()) {

			DOT D = queue.poll();

			for (int i = 0; i < 4; i++) {
				int cx = D.x + dx[i];
				int cy = D.y + dy[i];

				if (cx >= 0 && cx < M && cy >= 0 && cy < N) {
					if(map[cx][cy]==1&&!visited[cx][cy]) {
						visited[cx][cy]=true;
						queue.add(new DOT(cx,cy));
					}
				}
			}

		}
	}
}

class DOT {
	int x;
	int y;

	public DOT(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}