[Baekjoon] 9700_RAINFOREST CANOPY

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

---

< RAINFOREST CANOPY >

 

문제 풀이 

 

bfs를 사용하여 문제를 해결한다.

 

 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.LinkedList;
import java.util.Queue;
public class _9700_ { // RAINFOREST CANOPY
	static boolean arr[][];
	static int dx[] = { -1, 1, 0, 0, -1, -1, 1, 1 };
	static int dy[] = { 0, 0, -1, 1, -1, 1, -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));
		String str = "";
		int idx = 1;
		while ((str = bf.readLine()) != null) {
			int num = Integer.parseInt(str);
			arr = new boolean[num][num];
			for (int i = 0; i < num; i++) {
				String temp = bf.readLine();
				for (int j = 0; j < num; j++) {
					if (temp.charAt(j) == '0') {
						arr[i][j] = true;
					}
				}
			}
			int result = 0;
			for (int i = 0; i < num; i++) {
				for (int j = 0; j < num; j++) {
					if (!arr[i][j]) {
						result += 1;
						bfs(i, j);
					}
				}
			}
			bw.write("Case #" + (idx++) + ": " + result + "\n");
		}
		bw.flush();
	}
	private static void bfs(int i, int j) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { i, j });
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int k = 0; k < 8; 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;
					queue.add(new int[] { x, y });
				}
			}
		}
	}
}

변수)
arr : 배열 정보
dx, dy : 상, 하, 좌, 우, 대각선
idx : 테스트 케이스 번호
num : 배열 크기
result : 정답

 

입력이 주어지지 않을 때까지 계속해서 입력받는다. 배열 크기를 입력받고 배열 크기만큼 배열 정보를 입력받는다. 0일 경우 true로 저장한다. 배열을 전체 탐색하면서 아직 방문하지 않은 곳이라면 bfs 함수를 호출한다. 최종 정답은 bfs 함수를 호출한 횟수인 result를 출력한다.

 

bfs(좌표)

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

1) queue poll

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

---

---