1012 - 유기농배추(BFS)

---

package test;

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 Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		Queue<int[]> q = new LinkedList<>();

		// TestCase
		for (int testcase = 0; testcase < T; testcase++) {
			int count = 0;
			// 가로 세로 배추
			st = new StringTokenizer(br.readLine(), " ");
			int wide = Integer.parseInt(st.nextToken());
			int depth = Integer.parseInt(st.nextToken());
			int beachu = Integer.parseInt(st.nextToken());

			// 배열
			int[][] array = new int[depth][wide];
			boolean[][] visited = new boolean[depth][wide];

			// 배추 위치
			for (int i = 0; i < beachu; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int y = Integer.parseInt(st.nextToken());
				int x = Integer.parseInt(st.nextToken());

				array[x][y] = 1;
			}

			// 배추 찾기
			for (int i = 0; i < depth; i++) {
				for (int j = 0; j < wide; j++) {
					int value = array[i][j];

					if (visited[i][j] == false && value == 1) {
						q.offer(new int[] { i, j });
						while (!q.isEmpty()) {
							int[] point = q.poll();
							int x = point[0];
							int y = point[1];

							value = array[x][y];
							if (value == 0) {
								visited[x][y] = true;
							} else if (visited[x][y] == false && value == 1) {

								visited[x][y] = true;
								if (y + 1 < wide) {
									q.offer(new int[] { x, y + 1 });
								}
								if (y - 1 >= 0) {
									q.offer(new int[] { x, y - 1 });
								}
								if (x + 1 < depth) {
									q.offer(new int[] { x + 1, y });
								}
								if (x -1  >=0) {
									q.offer(new int[] { x - 1, y });
								}

							}
						}
						count++;
					} else if (value == 0) {
						visited[i][j] = true;
					}

				}
			}
			System.out.println(count);

		}

	}

}

 

문제풀이

KeyPoint: 1일때만 로직이 작동하고 (0일때는 방문여부만 체크하고 패스) 해당위치에서 방문하지 않은 4방향위치를 큐에 담는다 

큐를 꺼내서 해당위치가 1이면 다시 4방향을하고 0이면 패스 / 주변이 다 0이되면 그때 count++ 해준다.