[백준] 1012 유기농배추 #JAVA

 

BAEKJOON [1012] 유기농배추

---

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int m,n,k;
		int x,y;
		
		int round;
		int[] dx = {0,1,0,-1};
		int[] dy = {1,0,-1,0};
		
		round = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < round; i++) {
			String testCase = br.readLine();
			m = Integer.parseInt(testCase.split(" ")[0]);
			n = Integer.parseInt(testCase.split(" ")[1]);
			k = Integer.parseInt(testCase.split(" ")[2]);
			
			int[][] bat = new int[m][n];
			boolean[][] vis = new boolean[m][n];
			Queue<int[]> queue = new LinkedList<int[]>();
			int count = 0;
			
			for (int j = 0; j < k; j++) {
				String input = br.readLine();
				x = Integer.parseInt(input.split(" ")[0]);
				y = Integer.parseInt(input.split(" ")[1]);
				
				bat[x][y] = 1;
				
			}
			
			//bfs
			for (int q = 0; q < m; q++) {
				for (int p = 0; p < n; p++) {
					
					if(bat[q][p] == 1 && !vis[q][p]) {
						vis[q][p] = true;
						queue.add(new int[] {q,p});
						count++;	// 첫 시작점이 되는 점이 나오면 그룹의 개수 증가
					}
					
					while (!queue.isEmpty()) {
						
						int[] temp = queue.poll();
						
						for (int j = 0; j < 4; j++) {
							int nx = temp[0]+ dx[j];
							int ny = temp[1]+ dy[j];
							
							if(nx <0 || ny < 0 || nx >=m || ny >= n) continue; //범위
							if(vis[nx][ny]) continue;	//이미 방문한 곳
							if(bat[nx][ny] == 0) continue;	// 배추가 없는 곳
							
							vis[nx][ny] = true;
							queue.add(new int[] {nx,ny});
						}
					}
				}
			}
			System.out.println(count);
		}
	}

}

 

 

 

 

풀이

---

• BFS
• 양배추 그룹(?)은 bfs의 시작점을 찾을때 증가한다.
• 반복문이 많다보니 변수에 주의하자. i, j, k, p, q ...잘못넣어서 오래걸렸다.

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)