[BFS] 백준 1012 유기농 배추 JAVA

[문제출처 |  https://www.acmicpc.net/problem/1012 ]

그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색

---

기본적인 BFS 코드를 가지고 무난하게 적용해 볼 수 있는 문제였다.

단, 주의할 점은 가로길이, 세로길이, 가로좌표, 세로좌표의 순서로 받는다는 점!
보통 행->열 순으로 받는데 이 경우는 열->행 순으로 입력이 들어온다.

비슷한 문제로 백준 섬의 개수 문제가 있다.
이웃한(4방) 1의 뭉텅이가 몇개인지 찾는 문제였다.

 

---

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

// 통과 172ms
public class 유기농배추_1012 {

	static int T, M, N, K, map[][];
	static boolean[][] visited;
	static class Node {
		int r, c;

		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken()); // 열
			M = Integer.parseInt(st.nextToken()); // 행
			K = Integer.parseInt(st.nextToken()); // 배추 개수
			map = new int[M][N];
			visited = new boolean[M][N];
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int x = Integer.parseInt(st.nextToken()); // 가로 좌표
				int y = Integer.parseInt(st.nextToken()); // 세로 좌표
				map[y][x] = 1; // 여기에 배추가 있음
			}

			int cnt = 0;
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 1 && !visited[i][j]) {
						bfs(i, j);
						cnt++;
					}
				}
			}

			System.out.println(cnt);
		}

	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	private static void bfs(int sR, int sC) {
		Queue<Node> q = new LinkedList<Node>();

		q.offer(new Node(sR, sC));
		visited[sR][sC] = true;

		while (!q.isEmpty()) {
			Node curr = q.poll();
			int r = curr.r;
			int c = curr.c;

			for (int d = 0; d < 4; d++) {
				int nr = r + dr[d];
				int nc = c + dc[d];
				
				if(nr < 0 || nc < 0 || nr >= M || nc >= N)
					continue;
				if(visited[nr][nc])
					continue;
				if(map[nr][nc] == 0)
					continue;
				
				q.offer(new Node(nr, nc));
				visited[nr][nc] = true;
			}
		}
	}

}