알고리즘
백준 2583 영역 구하기
킨글
2022. 8. 28. 20:04
문제 접근
- 사각형으로 칠해진 부분 외에 영역이 몇개의 영역인지, 그리고 영역의 크기가 각각 얼마나 되는지를 구하는 문제이다.
- 다른 문제들에서는 친절하게 좌표값이 주어지지만 해당 문제는 꼭지점의 위치를 주기 때문에, 영역을 구하는 과정이 까다로웠다.
(둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다.)
그래서 아래와 같이 (c1,r1) ~ (c2,r2)를 구하고, 해당 영역을 모두 1로 채워주는 작업을 진행하였다.
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());
int r1 = M - y2;
int r2 = M - y1 - 1;
int c1 = x1;
int c2 = x2 - 1;
// (1.0) ~ (2,3)
// (0.1) ~ (3,1)
// (3,4) ~ (4,5)
for (int r = r1; r <= r2; r++) {
for (int c = c1; c <= c2; c++) {
maze[r][c] = 1;
}
}
}
헷갈렸던 점
- max 값을 static으로 주지 않고 dfs(x,y cnt)에서 가장 큰 cnt 값을 max 값으로 대입해주었더니 max 값이 잘못 나오는 현상이 있었다. 이것 때문에 한참 삽질했다.
- 이유를 찾아보니 이동할 경로가 없을 때에 소멸되기 때문이었다. 그래서 max 값을 static으로 주고 cnt를 없애버려서 처리했다.
반례
5 7 3
0 2 4 4
1 1 2 5
2 2 4 4
2
1 24
소스 코드
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class BOK_2583 {
public static void main(String[] args) throws IOException {
solution();
}
static int[][] maze;
static boolean[][] visited;
static int M;
static int N;
static int max;
static void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
maze = new int[M][N];
visited = new boolean[M][N];
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());
int r1 = M - y2;
int r2 = M - y1 - 1;
int c1 = x1;
int c2 = x2 - 1;
// (1.0) ~ (2,3)
// (0.1) ~ (3,1)
// (3,4) ~ (4,5)
for (int r = r1; r <= r2; r++) {
for (int c = c1; c <= c2; c++) {
maze[r][c] = 1;
}
}
}
ArrayList<Integer> array = new ArrayList<>();
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// 각 DFS마다의 넓이를 구하기 위해서 미리 필터링을 해준다.
if(!visited[i][j] && maze[i][j] != 1){
max = 0;
dfs(i, j);
array.add(max);
}
}
}
Collections.sort(array);
System.out.println(array.size());
for(int i=0; i<array.size(); i++){
if(i == array.size()-1)
System.out.print(array.get(i));
else
System.out.print(array.get(i)+" ");
}
}
static void dfs(int x, int y){
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
visited[x][y] = true;
max += 1;
for(int i=0; i<4; i++){
int nx = dx[i] + x;
int ny = dy[i] + y;
if(nx>=0 && ny>=0 && nx<M && ny <N) {
if(!visited[nx][ny] && maze[nx][ny] == 0) {
visited[nx][ny] = true;
dfs(nx, ny);
}
}
}
}
}