[백준] 1012. 유기농 배추(자바 JAVA)

[ 문제 ]  [백준] 1012. 유기농 배추(자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

# 접근 방법 및 풀이 

 

• BFS로 풀었다. 문제대로 이차원 배열 map[][]을 만들어 배추가 심어진 곳을 1로 표시한다.
• map을 탐색하며 값이 1일 경우 ans++시켜준다. 1을 발견하고, BFS 돌리면 상하좌우 인접한 1로표시된 영역에는 방문체크가 된다.
• 이렇게 탐색하며 방문하지 않은 새로운 1을 발견할 때마다 ans를 증가시키고 BFS를 돌면 된다. 

# 주의할 점 

 

• 배추 위치 X, Y 입력 주의

 

JAVA 코드

package Silver;

import java.awt.Point;
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 dr[] = {-1, 1, 0, 0};
	static int dc[] = {0, 0, -1, 1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			int ans = 0;
			StringTokenizer st = new StringTokenizer(in.readLine());
			int M = Integer.parseInt(st.nextToken());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			int map[][] = new int[N][M];
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(in.readLine());
				int X = Integer.parseInt(st.nextToken()); 
				int Y = Integer.parseInt(st.nextToken()); 
				map[Y][X] = 1;
			}
			boolean visit[][] = new boolean[N][M];
			Queue<Point> queue = new LinkedList<Point>();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(map[i][j] == 1 && !visit[i][j]) {
						ans++;
						visit[i][j] = true;
						queue.add(new Point(i, j));
						while(!queue.isEmpty()) {
							Point p = queue.poll();
							for (int d = 0; d < 4; d++) {
								int nr = p.x + dr[d];
								int nc = p.y + dc[d];
								if(nr < 0 || nc < 0 || nr >= N || nc >= M || visit[nr][nc] || map[nr][nc] == 0)
									continue;
								visit[nr][nc] = true;
								queue.add(new Point(nr, nc));
							}
						}
					}
				}
			}
			System.out.println(ans);
		}
	}
}

 

 

 

REVIEW