[Baekjoon] 11260_Cell Counting

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

---

< Cell Counting >

 

문제 풀이 

 

bfs를 활용하여 8방향에 아무것도 없는지 확인한다.

 

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;
import java.util.StringTokenizer;

public class _11260_ { // Cell Counting

	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;

		String str = "";

		while (!(str = bf.readLine()).equals("0 0")) {
			st = new StringTokenizer(str);

			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			char arr[][] = new char[r][c];
			Queue<int[]> queue = new LinkedList<>();

			for (int i = 0; i < r; i++) {
				str = bf.readLine();
				for (int j = 0; j < c; j++) {
					arr[i][j] = str.charAt(j);
					if (arr[i][j] == '#') {
						queue.add(new int[] { i, j });
					}
				}
			}
			bw.write(bfs(queue, arr) + "\n");
		}
		bw.flush();
	}

	private static int bfs(Queue<int[]> queue, char[][] arr) {

		int dx[] = { -1, 1, 0, 0, -1, -1, 1, 1 };
		int dy[] = { 0, 0, -1, 1, -1, 1, -1, 1 };

		int result = 0;

		while (!queue.isEmpty()) {
			int position[] = queue.poll();

			boolean flag = false;

			for (int i = 0; i < 8; i++) {
				int x = position[0] + dx[i];
				int y = position[1] + dy[i];

				if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && arr[x][y] == '#') {
					flag = true;
					break;
				}
			}

			if (!flag) {
				result += 1;
			}
		}
		return result;
	}
}

변수)
r, c : 행, 열
arr : 픽셀 데이터
queue : 세포 위치들
dx, dy : 8방향
result : 암세포 개수
position : 세포 위치
flag : 암세포 여부

 

Main

"0 0"이 입력되기 전까지 행, 열을 입력받는다. 행, 열만큼 픽셀 데이터를 입력받아 배열 arr에 저장하면서 세포라면 Queue에도 위치를 저장한다. 최종 bfs를 호출한 결괏값을 출력한다.

 

bfs(Queue <int []> queue, char [][] arr)

queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

2) 8방향 탐색 후 arr 범위 안이며 값이 '#'라면 암세포가 아니므로 flag를 true로 저장

3) 암세포라면 result+1

 

최종 result를 반환한다.

---

---