[백준] 2583. 영역 구하기 (자바 JAVA)

[ 문제 ]  [백준] 2583. 영역 구하기 (자바 JAVA)

 

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

2583번: 영역 구하기

---

# 접근 방법 및 풀이 

 

• 보통 0,0와 M,N은 맨 왼쪽 위부터 맨 오른쪽 아래로 생각하기 쉬운데 여기선 다르다.
• 0,0이 맨 왼쪽 아래고 M,N이 맨 오른쪽 위다.
• 그리고 숫자로 들어오는 값이 x, y를 좌표선상으로 생각해서 받아야한다. x는 가로축 y는 세로축이기 때문에 x는 열좌표 y는 행좌표이다.
• 주어진 네모 범위까지 1로 표시하고 bfs를 이용해서 풀었다.
• 자세한건 코드참조

# 주의할 점 

 

• 입력받을 때 좌표 범위 잘 확인해서 받기

 

JAVA 코드

package Silver;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj2583_영역구하기 {

	static int dr[] = {-1, 1, 0, 0};
	static int dc[] = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		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[M][N];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(in.readLine());
			int startC = Integer.parseInt(st.nextToken());
			int startR = M-1-Integer.parseInt(st.nextToken());
			int endC = Integer.parseInt(st.nextToken())-1;
			int endR = M-1-(Integer.parseInt(st.nextToken())-1);
			for (int r = startR; r >= endR; r--) {
				for (int c = startC; c <= endC; c++) {
					map[r][c] = 1;
				}
			}
		}//입력 끝
		boolean visit[][] = new boolean[M][N];
		Queue<Point> queue = new LinkedList<Point>();
		int depart = 0;
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(!visit[i][j] && map[i][j] == 0) {
					depart ++;
					visit[i][j] = true;
					queue.add(new Point(i, j));
					int cnt = 0;
					while(!queue.isEmpty()) {
						Point node = queue.poll();
						cnt++;
						for (int d = 0; d < 4; d++) {
							int nr = node.x + dr[d];
							int nc = node.y + dc[d];
							if( nr < 0 || nc < 0 || nr >= M || nc >= N || map[nr][nc] == 1 || visit[nr][nc])
								continue;
							visit[nr][nc] = true;
							queue.add(new Point(nr, nc));
						}
					}
					list.add(cnt);
				}
			}
		}
		Collections.sort(list);
		System.out.println(depart);
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i));
			if(i!=list.size()-1)
				System.out.print(" ");
		}
	}
}

 

 

 

REVIEW