[백준 / JAVA] 1012. 유기농 배추

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

1012번: 유기농 배추

 

---

💻 풀이 결과

 

💯 최종 코드

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

// 노드 생성
class Node {
	int r;
	int c;

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			int M = sc.nextInt(); // 가로 길이
			int N = sc.nextInt(); // 세로 길이
			int K = sc.nextInt();

			// 배추판 생성
			int[][] board = new int[N][M];
			for (int k = 0; k < K; k++) {
				int X = sc.nextInt();
				int Y = sc.nextInt();

				// 배추가 심어져있다.
				board[Y][X] = 1;
			}

			Queue<Node> queue = new LinkedList<>();
			boolean[][] visited = new boolean[N][M];
			// 지렁이 마리수
			int cnt = 0;

			// 1을 찾으러 가보자
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					// 방문하지 않은 1을 찾으면
					if (board[i][j] == 1 && !visited[i][j]) {
						// 벌레 한마리 추가
						cnt++;
						// 중심되는 배추
						queue.add(new Node(i, j));
						// 방문 처리
						visited[i][j] = true;

						// 중심 배추를 기준으로 4방탐색하며 인접한 배추들을 큐에 담는다.
						// 큐에 배추들이 다 사라지면 하나의 벌레가 갈 수 있는 배추들 모두 체크한 경우이다.
						while (!queue.isEmpty()) {
							// 배추를 하나 큐에서 빼고
							Node curr = queue.poll();

							// 뺀 배추를 중심으로 4방탐색
							int[] dr = { 0, 0, -1, 1 };
							int[] dc = { -1, 1, 0, 0 };

							for (int d = 0; d < 4; d++) {
								int nr = curr.r + dr[d];
								int nc = curr.c + dc[d];

								// 경계 검사
								if (nr < 0 || nc < 0 || nr >= N || nc >= M) {
									continue;
								}
								// 방문 검사
								if (visited[nr][nc]) {
									continue;
								}

								// 1이면 큐에 담는다.
								if (board[nr][nc] == 1) {
									queue.add(new Node(nr, nc));
									// 방문 처리
									visited[nr][nc] = true;
								}
							} // 4방탐색 끝
						} // while문 끝
					}
				}
			}
			System.out.println(cnt);
		} // 테케 끝
	} // main 끝
}

💬 풀이 과정

• 배추가 있는 위치에 표시한다.
• 중심이 되는 배추를 중심으로 BFS를 돌린다.
• 메모리 초과를 해결하기 위해 방문 체크와 방문 검사를 잘해준다.

💡 깨달은 점

1. 방문 체크와 방문 검사

• BFS를 돌릴 때는 visited 배열을 생성하여 방문 체크와 방문 검사를 잘해주어야 한다.
• 입력받은 보드 자체에서 수정해가며 방문 처리와 검사를 해 줄수도 있다.
• 두 방법에 대해 시간이나 메모리 차이는 크지 않았다.