[Eric's 백준] 2583번 - 영역 구하기 - Java

안뇽하세요! Eric 입니다!

오늘은 제가 bfs 문제를 하나 풀어보려 합니다!

문제는 백준 2583번 영역구하기 문제 입니다!

 

문제

해설

우선문제를 풀기위해서는 map 이라는 int[][] 배열을 만들어 줍니다.

이때의 int[][] map = new intp[M][N] 의 크기를 가집니다.

왜냐하면 해당 모눈종이가 입력의 첫번째 줄에서 그렇게 주어지므로

그리고 입력의 첫번째 줄에서 마지막으로 받는 K값은 

for 문을 통해서 K번 돌아서 입력에서 주어진 값을 map 에 표시합니다.

 

그리고 bfs 를 돌면서

해당 하는 영역의 면적을 구합니다.

bfs 를 돌면서 dx, dy를 통해서 시작점을 기준으로 상,하,좌,우 의 map 값이 0 이면 해당영역으로 이동하면서

영역의 크기를 증가시키고,

만약 map값이 1 이면 그쪽 방향으로는 이동하지 않고 끝냅니다.

이때, 이동하는 만큼의 양이 우리가 구하고자하는 면적의 크기를 area+1 씩 증가시키면 됩니다.

왜냐하면 해당 눈금의 면적이 1*1 이므로 area+1을 해주면 됩니다.

그리고 bfs를 구하는 조건이 될때마다 cnt+1을 해주어

나누어진 해당 부분의 개수를 구할 수 있습니다.

 

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.*;
	public class N2583 {
	static int N, M, K;
	static int[] dx = {0, 1, 0, -1}; // x값이 변화 가능한 범위
	static int[] dy = {1, 0, -1, 0}; // y값이 변화 가능한 범위
	static boolean[][] visited; // 해당 칸을 지내갔으면 true
	static int[][] map;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// 0. 입력
	StringTokenizer st = new StringTokenizer(br.readLine());
	M = Integer.parseInt(st.nextToken());
	N = Integer.parseInt(st.nextToken());
	K = Integer.parseInt(st.nextToken());
	map = new int[M][N];
	visited = new boolean[M][N];
	ArrayList<Integer> list = new ArrayList<>();
	int cnt = 0;
	// 1. map에 그림 표시 하기
	for (int i = 0; i < K; i++) {
	st = new StringTokenizer(br.readLine());
	int x1 = Integer.parseInt(st.nextToken());
	int y1 = Integer.parseInt(st.nextToken());
	int x2 = Integer.parseInt(st.nextToken());
	int y2 = Integer.parseInt(st.nextToken());
	// 주어진 사각형의 끝점을 각각 for문을 돌면서 면적 부분에 1로 표시를합니다.
	for (int y = y1; y < y2; y++) {
	for (int x = x1; x < x2; x++) {
	map[y][x] = 1;
	}
	}
	}
	// 2. bfs 돌기 및 영역 데이터 뽑기
	for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
	if (!visited[i][j] && map[i][j] == 0) {
	int area = bfs(new Point(i, j));
	list.add(area);
	cnt++;
	}
	}
	}
	// 4. 출력
	System.out.println(cnt);
	Collections.sort(list);
	for (int x : list) {
	System.out.print(x + " ");
	}
	br.close();
	}
	// 3. bfs 로 영역 구해보기
	public static int bfs(Point pt) {
	Queue<Point> queue = new LinkedList<>();
	queue.offer(pt);
	visited[pt.x][pt.y] = true;
	int area = 1; // area 가 1로 부터 시작한 이유는 이미 bfs로 들어왔다는거 자체가 1개 이상 이라는 것을 의미하므로
	while (!queue.isEmpty()) {
	Point tmp = queue.poll();
	int curX = tmp.x;
	int curY = tmp.y;
	for (int i = 0; i < 4; i++) {
	int nx = curX + dx[i];
	int ny = curY + dy[i];
	if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
	if (!visited[nx][ny] && map[nx][ny] == 0) {
	visited[nx][ny] = true;
	queue.offer(new Point(nx, ny));
	area++;
	}
	}
	}
	}
	return area; //해당 영역의 면적
	}
	}
	// 영역을 관리하기위해서 Point 라는 Class 로 관리
	class Point {
	int x;
	int y;
	public Point(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}

view raw N2583.java hosted with ❤ by GitHub