[Baekjoon] 6080_Bad Grass

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

---

< Bad Grass >

 

문제 풀이 

 

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 _6080_ { // Bad Grass
	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 R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		arr = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < C; j++) {
				if (Integer.parseInt(st.nextToken()) == 0) {
					arr[i][j] = true;
				}
			}
		}
		int result = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (!arr[i][j]) {
					result += 1;
					bfs(i, j);
				}
			}
		}
		System.out.println(result);
	}
	private static void bfs(int i, int j) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { i, j });
		arr[i][j] = true;
		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 });
				}
			}
		}
	}
}

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

 

배열 크기를 입력받는다. 배열 정보를 입력받으면서 0이라면 방문 여부를 true로 저장한다. 배열을 탐색하면서 아직 방문하지 않았다면 result에 1을 더하고 bfs를 호출한다. 최종 result를 출력한다.

 

bfs (시작 좌표)

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

1) queue poll

2) 상, 하, 좌, 우, 대각선을 탐색하며 배열 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시 및 queue에 추가한다. 

---

---