[Baekjoon] 30610_A-maze-ing Lakes

문제(출처: https://www.acmicpc.net/problem/30610)

---

< A-maze-ing Lakes >

 

문제 풀이 

 

bfs를 사용하여 1의 영역 개수와 크기를 구한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class _30610_ { // A-maze-ing Lakes
	static boolean arr[][];
	static ArrayList<Integer> result;
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		arr = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			String str = bf.readLine();
			for (int j = 0; j < M; j++) {
				if (str.charAt(j) == '0') {
					arr[i][j] = true;
				}
			}
		}
		result = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!arr[i][j]) {
					bfs(i, j);
				}
			}
		}
		Collections.sort(result);
		bw.write(result.size() + "\n");
		for (int num : result) {
			bw.write(num + " ");
		}
		bw.flush();
	}
	private static void bfs(int i, int j) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { i, j });
		arr[i][j] = true;
		int cnt = 1;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int k = 0; k < 4; k++) {
				int x = temp[0] + dx[k];
				int y = temp[1] + dy[k];
				if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && !arr[x][y]) {
					arr[x][y] = true;
					cnt += 1;
					queue.add(new int[] { x, y });
				}
			}
		}
		result.add(cnt);
	}
}

변수)
arr : 배열 정보
result : 1 크기
dx, dy : 상, 하, 좌, 우
N, M : 배열 크기

 

배열 크기를 입력받고 배열 크기만큼 배열 정보를 입력받는다. 배열 정보가 1일 경우 true로 저장한다. 배열을 탐색하면서 아직 방문하지 않은 곳이라면 bfs 함수를 호출한다. 오름차순으로 출력하기 위해 result를 정렬한 후 result의 크기와 result 값을 출력한다.

 

bfs(시작 위치)

큐에 시작 좌표를 저장한 후 큐가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

2) 4방향을 탐색하며 배열 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시와 cnt+1 및 queue에 추가

 

result ArrayList에 cnt 값을 저장한다.

---

---