백준2583_영역구하기 (java)

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

문제 풀이 방식

• 단지번호 붙이기 문제와 구하는 것은 같다.
• 다만, 우리가 평소에 배열로 만드는 map과 좌표가 달라서 이 부분이 좀 까다로웠다. 분명 첫 입력이 0,2 이고 4, 4인데 예시의 그림의 봐도 맞지않는것 같고, 이해가 안되서 입력을 받는 부분은 다른 블로그를 좀 참조했다.
• 직사각형의 범위는 모두 1로 바꾸어준다. 
• 직사각형으로 채워진 map이 만들어지면, 방문 한적이 없고 값이 0인 모든 칸들을 bfs로 탐색한다.
• 시작칸은 무조건 방문체크를 해주고 큐에 넣는다. 시작칸도 칸갯수에 포함하기 때문에 count = 1로 초기화 한다.
• 4가지 방향을 탐색하면서 방문체크를 해주고 count++를 해준다.
• 큐에 원소가 없으면 하나의 탐색을 끝낸 것이므로, count를 arraylist에 넣어준다.
• 모든 탐색이 끝나면 arraylist의 size를 출력하고, arraylist의 원소를 오름차순 정렬해서 출력한다.

주의할 점

• 2차원 배열의 좌표와 맞추기 위해 그림을 이런식으로 회전해서 봐야한다. 그래서 n이 가로가 되고 m이 세로가된다.
• 각 직사각형의 첫 좌표는 그대로 입력받으면 되지만 두 번째 좌표는 y(행)-1, x(열)-1이라고 생각해야한다.
• 영역마다 몇개의 칸이 있는지도 구해야하므로, 한 번 bfs를 돌때마다 count는 초기화 해줘야한다.

 

수도코드로 나타내보았다.

static int[][] map;
static boolean[][] visited;
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, -1, 0, 1};
static int n, m;
static ArrayList<Integer> list = new ArrayList<>();

class Main {
    void main() {
        n = read();
        m = raed();
        int k = read();
        map = new int[m][n]; // 가로세로를 변경
        visited = new boolean[m][n];

        for(i=0; i<k; i++) {
            new StringTokenizer(read);
            y1 = nextToken();
            x1 = nextToken();
            y2 = nextToken();
            x1 = nextToken();
            // 입력으로 들어온 직사각형 범위는 1로 표시. i<y2이면 y2-1까지를 말함.
            for (int i = y1; i < y2; i++) { 
                for (int j = x1; j < x2; j++) {
                    map[i][j] = 1;
                }
            }
        }

        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
            	// 직사각형의 범위가 아니고 방문한적없는 곳부터 탐색
                if(map[i][j] == 0 && !visited[i][j]) { 
                    bfs(i, j);
                }
            }
        }

        Collections.sort(list); // 오름차순 출력해야하므로 정렬
        sb.append(list.size + "\n"); // list의 사이즈가 곧 영역의 개수
        
        for(Integer x : list) {
            sb.append(x + " "); // list의 값을 출력
        }
        
        print(sb);
        
    }
    void bfs(int y, int x) {
        int count = 1; // 영역별 칸의 개수 초기화 - 시작칸이므로...
        Queue<Position> que = new LinkedList<>();
        que.add(new Position(y, x));
        visited[i][j] = true;

        while(!que.isEmpty()) {
            Position now = que.poll();

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

                if(valCheck(ny, nx) && !visited[ny][nx] && map[ny][nx] == 0) {
                    que.add(new Position(ny, nx));
                    visited[ny][nx] = true;
                    count++;
                }
            }
        }
        // 큐사이즈가 없으면 탐색할 곳이 없다는 뜻(=하나의 영역을 다 탐색함)
        // 지금까지 센 칸의 갯수를 list에 담음
        list.add(count); 
    }

    boolean valCheck(int y, int x) {
        if(y < 0 || y >= m || x < 0 || x >= n) return false;
        return true;
    }
}

class Position {
    int y;
    int x;

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