[Baekjoon] 15092_Sheba’s Amoebas

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

---

< Sheba's Amoebas >

 

문제 풀이 

 

bfs 알고리즘을 사용하여 문제를 해결한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class _15092_ { // Sheba’s Amoebas
	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));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		arr = new boolean[m][n];
		for (int i = 0; i < m; i++) {
			String str = bf.readLine();
			for (int j = 0; j < n; j++) {
				if (str.charAt(j) == '.') {
					arr[i][j] = true;
				}
			}
		}
		int result = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (!arr[i][j]) {
					result += 1;
					bfs(i, j);
				}
			}
		}
		System.out.println(result);
	}
	private static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y });
		arr[x][y] = true;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8; j++) {
					int a = temp[0] + dx[i];
					int b = temp[1] + dy[i];
					if (a >= 0 && a < arr.length && b >= 0 && b < arr[0].length && !arr[a][b]) {
						arr[a][b] = true;
						queue.add(new int[] { a, b });
					}
				}
			}
		}
	}
}

변수)
m, n : 배열 크기
arr : 배열
dx, dy : 상, 하, 좌, 우, 대각선
result : 결과

 

배열 크기를 입력받아 배열 크기만큼 정보를 입력받으며 '.'인 경우 true로 저장한다. 배열을 전체 탐색하면서 false라면 bfs 함수를 호출한다. 최종 result를 출력한다.

 

bfs(int x, int y)

Queue에 시작 위치를 저장하고 arr에 true로 저장한다. queue가 빌 때까지 다음 과정을 반복한다.

1) queue poll

2) 8방향으로 탐색 후 배열 범위 안이며 아직 방문하지 않았다면 방문 표시 및 queue에 추가

---

---