[Baekjoon] 6186_Best Grass

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

---

< Best 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 _6186_ { // Best Grass
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static boolean visited[][];
	static int r, c;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

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

		visited = new boolean[r][c];
		for (int i = 0; i < r; i++) {
			String str = bf.readLine();
			for (int j = 0; j < c; j++) {
				if (str.charAt(j) == '.') {
					visited[i][j] = true;
				}
			}
		}

		int result = 0;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (!visited[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 });

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

			for (int i = 0; i < 4; i++) {
				int a = temp[0] + dx[i];
				int b = temp[1] + dy[i];
				if (a >= 0 && a < r && b >= 0 && b < c && !visited[a][b]) {
					visited[a][b] = true;
					queue.add(new int[] { a, b });
				}
			}
		}
	}
}

변수)
r, c : 행, 열
visited : 방문 여부
result : 풀 묶음 개수

 

행, 열을 입력받는다. 정보를 입력받으면서 풀이 아니라면 방문 여부를 true로 저장한다. visited 전체를 탐색하면서 아직 방문하지 않은 곳을 기준으로 bfs를 호출한다. 

 

총 bfs 호출 횟수를 정답으로 출력한다.

 

bfs(int x, int y)

Queue에 [x, y]를 저장한다. Queue가 빌 때까지 다음 과정을 반복한다.

1) queue에서 poll

2) 상하좌우 탐색하여 아직 방문하지 않은 곳이라면 방문 표시 및 queue에 저장

 

---

---