[알고리즘] 백준 2583 영역 구하기

www.acmicpc.net/problem/2583

2583번: 영역 구하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_2583 {

    static int m;
    static int n;
    static int k;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");

        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];

        for (int i = 0; i < k; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");
            Location left = new Location(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
            Location right = new Location(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

            for (int j = right.y - 1; j >= left.y; j--) {
                for (int k = left.x; k < right.x; k++) {
                    map[m - 1 - j][k] = 1;
                }
            }
        }

        List<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 1) {
                    list.add(bfs(new Location(i, j, 0)));
                }
            }
        }

        Collections.sort(list);
        System.out.println(list.size());

        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }

    public static int bfs(Location current) {
        Queue<Location> queue = new LinkedList<Location>();
        queue.add(current);
        visited[current.x][current.y] = true;
        map[current.x][current.y] = 1;
        int count = 1;

        while (!queue.isEmpty()) {
            Location location = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = location.x + dx[i];
                int ny = location.y + dy[i];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    if (map[nx][ny] == 0 && !visited[nx][ny]) {
                        queue.add(new Location(nx, ny, 0));
                        map[nx][ny] = 1;
                        visited[nx][ny] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    static class Location {
        int x;
        int y;
        int value;

        public Location(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }

    }

}

 

직사각형이 그려진 영역을 제외하고, 섹션별로 숫자를 세는 문제이다.

 

문제 푸는것보다 입력받는게 훨씬 어려웠다.

 

문제의 좌표와 행렬 좌표가 아예 반대라 짜증났었는데, 다시 보니 입력을 굳이 저렇게 똑같이 안받아도

 

위치만 다를뿐 섹션은 똑같이 나뉘기 때문에 어짜피 똑같은 문제였다.

 

나는 고생한게 억울해서 입력을 똑같이 받고 풀었다.

 

직사각형이 그려지는 부분의 인덱스값을 1로 한 후

 

map의 [0][0] 부터 반복문을 통해 인덱스값이 0인 경우에 bfs를 돌려서 문제를 해결했다.

 

입력받는 것만 해결하면 아주 쉬운 문제이다.

 

dfs로 풀었으면 아마 코드가 짧았을것이다.