[BaekJoon 1012번 / JAVA] 유기농 배추

Question

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

---

💡 Solution

BFS로 풀이하였으며, 토마토 문제와 같이 BFS 유형을 공부하기에 적합한 문제인 거 같습니다. 큐를 만들어 x, y 좌표(배추가 있는 좌표)를 넣고 해당 좌표를 기준으로 상하좌우로 움직입니다. 움직인 좌표에 배추가 있다면 또다시 해당 좌표를 큐에 넣어 상하좌우로 이동하며 탐색하는 방식입니다.

 

💻 Code

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 BJ1012 {
	static int M, N, K;
	static int[][] map;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	static boolean[][] visited;
	static int count;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			map = new int[M][N];
			visited = new boolean[M][N];
			count = 0;
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				map[x][y] = 1;
			}
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 1 && !visited[i][j]) {
						solve(i, j);
						count++;
					}
				}
			}
			System.out.println(count);
		}

	}
	
	public static void solve(int x, int y) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {x, y});
		visited[x][y] = true;
		
		while(!queue.isEmpty()) {
			int now_x = queue.peek()[0];
			int now_y = queue.peek()[1];
			queue.poll();
			
			for (int i = 0; i < 4; i++) {
					int nx = now_x + dx[i];
					int ny = now_y + dy[i];
					if (nx >= 0 && nx < M && ny >= 0 && ny < N && !visited[nx][ny]) {
						if (map[nx][ny] == 1) {
							visited[nx][ny] = true;
							queue.add(new int[] {nx, ny});
						}
					}	
			}
		}
	}
}