[알고리즘/백준] 1012 유기농 배추 - 자바(Java), BFS

[알고리즘/백준] 1012 유기농 배추 - 자바(Java), BFS

문제

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

풀이 코드

BFS를 사용하여 풀이(DFS로도 풀이 가능)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; static class Pos { int x; int y; public Pos(int x, int y) { this.x = x; this.y = y; } } public static void bfs(int[][] board, int x, int y, int n, int m) { Queue q = new LinkedList<>(); q.offer(new Pos(x, y)); board[x][y] = 0; while (!q.isEmpty()) { Pos pos = q.poll(); for (int i = 0; i < 4; i++) { int nx = pos.x + dx[i]; int ny = pos.y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 1) { q.offer(new Pos(nx, ny)); board[nx][ny] = 0; } } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int t = Integer.parseInt(br.readLine()); for (int i = 0; i < t; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int m = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int[][] board = new int[n][m]; for (int j = 0; j < k; j++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); board[y][x] = 1; } //필요한 최소 흰지렁이 마리 수 int answer = 0; //반복문을 돌며 1(배추)을 발견하면 BFS를 진행하여 배추 흰지렁이 한마리로 커버할 수 있는 인접한 범위를 구한다. for (int j = 0; j < n; j++) { for (int l = 0; l < m; l++) { if (board[j][l] == 1) { bfs(board, j, l, n, m); answer++; } } } sb.append(answer).append("

"); } System.out.println(sb); } }

728x90

from http://developer-hm.tistory.com/207 by ccl(A) rewrite - 2021-10-29 20:28:05