[BJ] 백준 1012 유기농 배추 (JAVA)

문제

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

 

풀이 방법​

실버 레벨에 해당하는 문제로 배추의 위치가 주어지고, 인접해있는 배추를 탐색해서 몇개의 배추 구역이 있는지 개수를 구하면 되는 문제다. 
4방탐색으로 모든 방향을 돌면서 배추가 존재하는지, 방문했는지의 여부를 판단해야하기 때문에 BFS알고리즘을 사용해서 구현했다.
우선 배추의 위치는 입력값을 토대로 1로 설정해줬다.
그리고 이제 땅을 모두 돌면서 배추가 존재하면서 아직 방문하지 않은 경우 새로운 구역을 발견한 것이기 때문에 구역의 수에 1를 추가해줬다.
인접해있는 배추들을 모두 찾아줘야하기 때문에 Queue를 사용해서 BFS를 구현해줬다.
4방탐색을 하면서 배추이면서 아직 방문하지 않는 칸이 있다면 큐에 추가해주고, 방문 배열을 true로 변경해줬다.

 

제출 코드

import java.io.*;
import java.util.*;

public class BJ_1012_유기농배추 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		int[][] move = {{-1,0},{0,1},{1,0},{0,-1}}; //북, 동 , 남 , 서
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			String[] str = br.readLine().split(" "); 
			int N = Integer.parseInt(str[1]); //가로 세로 배추개수 저장
			int M = Integer.parseInt(str[0]);
			int K = Integer.parseInt(str[2]);
			int[][] map = new int[N][M];
			for (int i = 0; i < K; i++) { //배추 위치 저장
				str = br.readLine().split(" ");
				int r = Integer.parseInt(str[1]);
				int c = Integer.parseInt(str[0]);
				map[r][c] = 1;
			}
			int cnt =0;
			boolean [][] visit = new boolean[N][M]; //방문 체크
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(map[i][j]==1 && !visit[i][j]) { //배추가 있고, 아직 방문하지 않은 배추이면
						cnt++;  //벌레수 추가
						Queue<int[]> que = new LinkedList<>();
						que.add(new int[] {i,j}); //첫 시작 위치
						visit[i][j] = true;
						while(!que.isEmpty()) { //bfs시작
							int[] t = que.poll();
							for (int l = 0; l < 4; l++) { //4방 탐색
								int ni = t[0] + move[l][0];
								int nj = t[1] + move[l][1];
								if(ni>=0 && ni<N && nj>=0 && nj<M 
										&& map[ni][nj]==1 &&!visit[ni][nj]) { //배추이면서 아직 방문하지 않았으면 
									que.add(new int[] {ni,nj}); //큐에 추가
									visit[ni][nj]=true; //방문 배열 true로 변경
								}
							}
						}
					}
				}
			}
			System.out.println(cnt);
		}
	}
}