백준 1012 유기농 배추

백준 1012 유기농 배추

1. 문제 링크

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

1012번: 유기농 배추

 

2. 문제 해결에 대한 아이디어

• input으로 들어온 2차원 배열을 순회하며 1(배추가 심어져 있는 땅)에 대해 BFS를 수행한다
• BFS를 수행한 카운트를 출력한다.

 

3. 코드

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

public class Main {

	static int M, N, K;
	static int[][] board;
	static boolean[][] visited;
	static Queue<Pair> q = new LinkedList<>();
	static int worm;
	static int[] dirY = {0, 0, 1, -1};
	static int[] dirX = {1, -1, 0, 0};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine().split(" ")[0]);
		for (int t = 0; t < T; t++) {
			String[] mnk = br.readLine().split(" ");
			M = Integer.parseInt(mnk[0]);
			N = Integer.parseInt(mnk[1]);
			K = Integer.parseInt(mnk[2]);

			board = new int[N][M];
			visited = new boolean[N][M];
			worm = 0;
			
			for (int k = 0; k < K; k++) {
				int y, x;
				String[] yx = br.readLine().split(" ");
				y = Integer.parseInt(yx[1]);
				x = Integer.parseInt(yx[0]);
				
				board[y][x] = 1;
				q.add(new Pair(y, x));
			}
			
			while(!q.isEmpty()) {
				Pair now = q.poll();
				if(visited[now.y][now.x])
					continue;
				BFS(now);
				++worm;
			}
			
			System.out.println(worm);
		}
	}
	
	static void BFS(Pair pair) {
		Queue<Pair> tq = new LinkedList<>();
		tq.add(pair);
		visited[pair.y][pair.x] = true;
		while(!tq.isEmpty()) {
			Pair now = tq.poll();
			
			for(int i = 0 ; i < 4 ; i++) {
				int yy = now.y + dirY[i];
				int xx = now.x + dirX[i];
				if(xx < 0 || yy < 0 || xx >= M || yy >= N || visited[yy][xx] || board[yy][xx] != 1)
					continue;
				visited[yy][xx] = true;
				tq.add(new Pair(yy, xx));
			}
		}
		
	}
}

class Pair{
	public int y, x;

	public Pair(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}

}

 

4. 채점 결과

 

5. 느낀 점

• BFS를 사용하는 아주 기본적인 유형이었다.