[Java] 백준 1012번 (유기농 배추)

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

1012번: 유기농 배추

 

 

전형적인 bfs 문제이다. Queue를 사용해서 풀었다.

​

먼저 초기화 작업이다.

문제에 나와있듯이 각 케이스마다 m, n, k를 구해야 한다.

StringTokenizer를 사용해 변수에 값을 넣었다.

t = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());

 

 

 

그리고 이 변수들을 사용해

0,과 1이 들어간 배추자리(없으면 0, 있으면 1)

그 배열을 방문했는지 체크하는 boolean 배열

그리고 배열을 탐색할 때 쓰는 Queue를 선언하였다.

maps = new int[m][n];
visited = new boolean[m][n];
queue = new LinkedList<>();

 

 

그 다음 배추가 있는자리 ( 배열의 값이 1) 이거나

방문하지 않은 배열이라면 그 좌표값을 매개변수로 하는 bfs라는 메소드를 실행하는 코드이다.

실행할때 마다 벌레의 갯수를 세는 cnt가 1씩 증가 한다.

for (int j = 0; j < maps.length; j++) {
	for (int z = 0; z < maps[0].length; z++) {
		if(!visited[j][z] && maps[j][z] == 1) {
			bfs(j, z);
			cnt++;
		}
	} //for
} // for

 

 

bfs 메서드이다.

매개변수로 받은 좌표값(x값, y값)을 가지고 새로운 int형 배열을 만들어 Queue에 넣는다.

그리고 그 좌표들은 방문을 했으니 visited[]에(방문 체크 boolean형 배열) true를 넣는다.

그 다음 while문을 실행하는데 poll 함수를 통해 현재 좌표를 갖고온뒤

미리 움직일 좌표를 더하고 만약 그 움직일 좌표가 0보다 작거나 배열의 크기보다 크면 continue하기로 한다.

그리고 방문하지 않았거나 배추가 있는자리 ( 움직일 좌표의 값이 1 일시) 다시 Queue에 움직일 좌표를 배열로 넣는다.

public static void bfs(int x, int y) {
		queue.add(new int[] {x, y});
		visited[x][y] = true;
		
		while (!queue.isEmpty()) {
			int current[] = queue.poll();
			int cx = current[0];
			int cy = current[1];
			
			for (int i = 0; i < 4 ; i++) {
				int mx = cx + dx[i];
				int my = cy + dy[i];
				
				if (mx < 0 || mx >= maps.length || my < 0 || my >= maps[0].length) {
					continue;
				} // if
				if(!visited[mx][my] && maps[mx][my] == 1) {
					queue.add(new int[] {mx, my});
					visited[mx][my] = true;
				}
			} // for
		} // while
		
} // bfs

 

 

 

아래는 전체 코드이다.

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

public class Main {
	
	static final int dx[] = {-1, 0, 1, 0};
	static final int dy[] = {0, 1, 0, -1};
	static int maps[][] ;
	static boolean visited[][];
	static Queue<int[]> queue;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int i = 0; i < T; i++) {
			// init
			st = new StringTokenizer(br.readLine());
			int m = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			maps = new int[m][n];
			visited = new boolean[m][n];
			queue = new LinkedList<>();
			int cnt = 0;
			
			for (int j = 0; j < k; j++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				maps[x][y] = 1;
			}
			
			for (int j = 0; j < maps.length; j++) {
				for (int z = 0; z < maps[0].length; z++) {
					if(!visited[j][z] && maps[j][z] == 1) {
						bfs(j, z);
						cnt++;
					}
				} //for
			} // for
			
			list.add(cnt);
		} // for
		
		for (int i : list) {
			System.out.println(i);
		}
		
	} // main
	public static void bfs(int x, int y) {
		queue.add(new int[] {x, y});
		visited[x][y] = true;
		
		while (!queue.isEmpty()) {
			int current[] = queue.poll();
			int cx = current[0];
			int cy = current[1];
			
			for (int i = 0; i < 4 ; i++) {
				int mx = cx + dx[i];
				int my = cy + dy[i];
				
				if (mx < 0 || mx >= maps.length || my < 0 || my >= maps[0].length) {
					continue;
				} // if
				if(!visited[mx][my] && maps[mx][my] == 1) {
					queue.add(new int[] {mx, my});
					visited[mx][my] = true;
				}
			} // for
		} // while
		
	} // bfs
} // class