백준 2583번 : 영역 구하기 (그래프에 도형)
이번 문제는 m*n 크기의 그래프가 주어지고 해당 그래프 내에 직사각형을 그려, 겹치는 부분 상관없이 직사각형의 내부를 제외한 나머지 부분의 영역 개수와 각 영역의 넓이를 구하는 문제이다.
백준 2583 : 영역 구하기 문제에서 발췌한 테스트 케이스의 그래프는 아래와 같다. 
위 그래프의 테스트 케이스는 아래와 같다.
1
2
3
4
5
6
7
8
9
input
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2
out put
3
1 7 13
즉 m, n, k(직사각형의 개수) 를 입력 받고, 다음부터 k번째 줄까지 직사각형의 시작, 끝 좌표를 입력 받는다.
그러므로, 각 좌표에 맞게 직사각형을 그래프에 그리고 남은 영역을 파악할 수 있다.
문제에서 요구하는 결과값은 직사각형이 없는 영역의 개수, 해당 각 영역의 넓이기 때문에 개수를 세어줄 위치를 적절히 잡아주어야하는데
단지번호 붙이기 문제에서 확인할 수 있다.
각각,
- 탐색을 시작할 때
- DFS의 경우 함수로 진입할 때 (재귀함수이기 때문)
- BFS의 경우 함수로 진입할 때 (시작좌표를 포함하기 위함)와 다음 좌표로 진입할 때
이렇게 세 가지 위치를 잡을 수 있다.
여기서 각 개수를 count 변수를 활용하였으며, ArrayList에 담아 영역의 개수와 각 영역의 넓이를 저장했다.
탐색 관련 로직과 개수를 세어주는 로직은 각각
유기농 배추
단지번호 붙이기 문제에서 확인할 수 있기 때문에 관련된 내용을 서술하지 않을 것이다.
다만, 입력 값을 가공하여 그래프에 도형을 그려주어야 하는데, 이 부분에서 헤맸기 때문에 내용을 작성할 것이다.
그래프에 직사각형의 시작 좌표와 끝 좌표를 가지고서 그려주어야하는데, 나는 이 부분을 각 x,y 좌표를 받아 직사각형이 위치한 좌표를 1로 초기화했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 그래프 - 직사각형 위치를 1로 표현
while (k-- > 0) {
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());
for (int i = m - y2; i < m - y1; i++) {
for (int j = x1; j < x2; j++) {
arr[i][j] = 1;
}
}
}
여기서 x1,y1은 시작 좌표, x2, y2는 종료 좌표를 뜻하며, m은 배열의 y축 크기, n은 배열의 x축 크기이다.
이중 for문을 실행해 모든 좌표를 순회하며 직사각형을 삽입할 것이다.
1
for (int i = m - y2; i < m - y1; i++)
외부 반복문의 경우, 그래프에서 y축은 위로 갈수록 값이 증가하지만,
배열에서는 아래로 갈수록 인덱스가 증가하기 때문에 y좌표를 배열의 인덱스로 활용하기 위해서
뒤집어주어야 한다.
이러한 이유로 인해 y축의 최대인 m에서 입력 받은 y 좌표를 뺀 값을 사용한다.
이를 통해 직사각형의 시작부터 y축 길이 만큼 순회할 수 있다.
다음으로
1
for (int j = x1; j < x2; j++)
내부 반복문의 경우, 그래프의 x축과 배열의 x축은 방향이 같다.
다시 말해, 둘 다 x축이 좌에서 우로 진행된다는 뜻이다.
그러므로, x좌표를 그대로 배열의 인덱스로 사용한다.
이 반복문을 통해 그래프 내부에 각 직사각형 위치는 1로 채워진다.
나머지는 탐색과 카운팅인데, 이 부분은 앞서 말했듯이 이전 문제들과 동일하기 때문에 넘어간다.
마지막으로 문제에서 주의할 점은 결과 값은 오름차순 정렬되어야 한다는 것이다.
전체 소스 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[] dx = new int[]{-1, 0, 1, 0};
static int[] dy = new int[]{0, 1, 0, -1};
static int[][] arr;
static boolean[][] visited;
static int m, n, count = 0;
public static void main(String[] args) throws java.io.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());
// 그래프, 방문 여부 초기화
arr = new int[m][n];
visited = new boolean[m][n];
// 그래프 - 직사각형 위치를 1로 표현
while (k-- > 0) {
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());
for (int i = m - y2; i < m - y1; i++) {
for (int j = x1; j < x2; j++) {
arr[i][j] = 1;
}
}
}
// 탐색 - 0인 경우 이동 가능
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 0 && !visited[i][j]) {
// dfs(i, j);
bfs(i, j);
list.add(count);
count = 0;
}
}
}
// 오름차순 정렬
Collections.sort(list);
System.out.println(list.size());
StringBuilder sb = new StringBuilder();
for (int v : list) {
sb.append(v).append(" ");
}
System.out.println(sb);
}
public static void dfs(int x, int y) {
visited[x][y] = true;
count++;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
if (arr[nx][ny] == 0 && !visited[nx][ny]) {
dfs(nx, ny);
}
}
}
}
public static void bfs (int x, int y) {
Queue<int[]> q = new LinkedList<>();
visited[x][y] = true;
q.offer(new int[]{x,y});
count++;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
if (arr[nx][ny] == 0 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
count++;
}
}
}
}
}
}
위에서 아래로 각각 BFS, DFS 결과이다.
그래프에 직사각형을 표현하려면 이 문제로 돌아와서 참고하면 된다.
이외에는 작성하지 않아서 간단하긴 하지만 이 그래프 내 도형 그리는 로직 때문에 작성한 글이라 크게 상관없을 것이다.
그래프 안에 마름모 등 또 다른 도형을 그리기위한 초석이 되지 않을까 싶다.