백준 2583 - 영역 구하기

Java

2583 번 - 영역 구하기

문제

접근 방법

«««< HEAD

영역을 표시하는 것이 핵심인 문제였다.
왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값을 받아 반복문을 통해 범위만큼 1로 바꾸어 주어 영역을 표시해 주었다.

여기서 오른쪽 위 꼭짓점은 1씩 차감하는 것을 놓치면 안된다.

이후 BFS를 통해 넓이를 구하고, 그 넓이를 List에 저장 후 정렬하여 문제를 해결하였다.

335fb3027b7baa39619109abe387ef513d163f45

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, k, areaCnt;
	static int[][] map;
	static List<Integer> area;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
<<<<<<< HEAD

    	map = new int[n][m];

=======
    	
    	map = new int[n][m];
    	
>>>>>>> 335fb3027b7baa39619109abe387ef513d163f45
    	int y1, x1, y2, x2;
    	for(int idx = 0; idx < k; idx++) {
    		stk = new StringTokenizer(br.readLine());
    		x1 = stoi(stk.nextToken());
    		y1 = stoi(stk.nextToken());
    		x2 = stoi(stk.nextToken()) - 1;
    		y2 = stoi(stk.nextToken()) - 1;
<<<<<<< HEAD

=======
    		
>>>>>>> 335fb3027b7baa39619109abe387ef513d163f45
    		for(int i = y1; i <= y2; i++) {
    			for(int j = x1; j <= x2; j++) {
    				map[i][j] = 1;
    			}
    		}
    	}
<<<<<<< HEAD

=======
    	
>>>>>>> 335fb3027b7baa39619109abe387ef513d163f45
    	area = new ArrayList<Integer>();
    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < m; j++) {
    			if(map[i][j] == 0) {
    				area.add(BFS(i,j));
    			}
    		}
    	}
<<<<<<< HEAD

    	System.out.println(areaCnt);

    	Collections.sort(area);

    	for(int num : area)
    		System.out.print(num + " ");

    	br.close();
	}

=======
    	
    	System.out.println(areaCnt);
    	
    	Collections.sort(area);
    	
    	for(int num : area)
    		System.out.print(num + " ");
    	
    	br.close();
	}
	
>>>>>>> 335fb3027b7baa39619109abe387ef513d163f45
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
<<<<<<< HEAD

    static int dy[] = {-1,1,0,0};
	static int dx[] = {0,0,-1,1};

=======
    
    static int dy[] = {-1,1,0,0};
	static int dx[] = {0,0,-1,1};
	
>>>>>>> 335fb3027b7baa39619109abe387ef513d163f45
    private static int BFS(int y, int x) {
    	areaCnt++;
		int count = 1;
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {y,x});
		map[y][x] = 1;
<<<<<<< HEAD

=======
		
>>>>>>> 335fb3027b7baa39619109abe387ef513d163f45
		int[] q;
		int ny,nx;
		while(!queue.isEmpty()) {
			q = queue.poll();
			y = q[0];
			x = q[1];
<<<<<<< HEAD

=======
			
>>>>>>> 335fb3027b7baa39619109abe387ef513d163f45
			for(int i = 0; i < 4; i++) {
				ny = y + dy[i];
				nx = x + dx[i];
				if(isIn(ny,nx) && map[ny][nx] == 0) {
					map[ny][nx] = 1;
					count++;
					queue.add(new int[] {ny,nx});
				}
			}
		}
<<<<<<< HEAD

		return count;
	}

=======
		
		return count;
	}
	
	
>>>>>>> 335fb3027b7baa39619109abe387ef513d163f45
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점