[Java] 백준(실버-1) 2583번 - 영역 구하기
문제 풀이
이번 문제는 너비 우선 탐색 BFS를 이용해 풀 수 있는 문제이다.
아이디어 도출
일반적인 BFS 문제들과 유사하나, 직사각형의 위치를 먼저 갱신하고 BFS 탐색을 진행하도록 구현하면 된다.
그래서 문제에서 주어지는 4개의 x,y좌표를 통해 직사각형의 위치를 갱신하는 것이 핵심이다. 문제에서는 왼쪽 아래 x,y 좌표와 오른쪽 위 x,y죄표를 어떻게 직사각형 위치만큼 배열에 기록할 수 있을까?
아래 예시를 통해 살펴보자.
1
2
3
4
M=5, N=7, K=3
0 2 4 4
1 1 2 5
4 0 6 2
- 왼쪽 x 좌표부터 오른쪽 x 좌표까지 0 ~ 4, 왼쪽 y 좌표부터 오른쪽 y 좌표까지 2 ~ 4
- 왼쪽 x 좌표부터 오른쪽 x 좌표까지 1 ~ 2, 왼쪽 y 좌표부터 오른쪽 y 좌표까지 1 ~ 5
- 왼쪽 x 좌표부터 오른쪽 x 좌표까지 4 ~ 6, 왼쪽 y 좌표부터 오른쪽 y 좌표까지 0 ~ 2
위와 같이 x와 y좌표의 왼쪽, 오른쪽 값의 위치일 때면 직사각형의 범위 내에 있는 것이라고 볼 수 있다! 그래서 4개의 꼭지점을 입력받을 때 직사각형의 위치만큼 배열을 갱신할 수 있게 된다.
이제 문제풀이를 위한 전체적인 흐름을 살펴보자.
- M*N 크기의 배열에서 4개의 꼭지점을 입력받아 직사각형의 위치만큼 1로 갱신한다.
- 해당 배열을 가지고 BFS 너비 우선 탐색을 진행하여 분리된 영역의 갯수와 각 영역별 넓이를 구한다.
꼭지점을 가지고 직사각형 범위만 찾아낼 수 있다면, BFS를 수행하는 로직은 쉽다고 볼 수 있다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
import java.io.*;
import java.util.*;
class Main {
// 상,하,좌,우로 탐색할 dx,dy 배열 선언
static int[] dx = new int[]{1, 0, -1, 0};
static int[] dy = new int[]{0, 1, 0, -1};
// 방문 배열 및 직사각형 위치를 갱신할 입력배열 선언
static boolean[][] visited;
static int[][] arr;
// 배열의 크기와 직사각형 위치 갯수 변수 선언
static int N, M, K;
// 영역 총 갯수 선언
static int totalCnt;
// 영역별 넓이를 담을 List 선언
static ArrayList<Integer> areaCnts;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
// 입력 배열 및 방문 배열 초기화
arr = new int[N][M];
visited = new boolean[N][M];
// 4개의 꼭지점을 입력받아 arr 배열에 직사각형을 놓는다.
for(int i=0; i<K; i++) {
st = new StringTokenizer(br.readLine());
int left_x = Integer.parseInt(st.nextToken());
int left_y = Integer.parseInt(st.nextToken());
int right_x = Integer.parseInt(st.nextToken());
int right_y = Integer.parseInt(st.nextToken());
// 직사각형 꼭지점을 이용해 배열에 직사각형 위치를 1로 갱신한다.
for(int x=left_x; x<right_x; x++) {
for(int y=left_y; y<right_y; y++) {
arr[x][y] = 1;
}
}
}
// 영역의 총 갯수를 구하기 위해 초기화
totalCnt = 0;
// 영역별 넓이를 담기위한 List 초기화
areaCnts = new ArrayList<>();
// MXN만큼 순회하며 bfs 함수 호출하여 영역별 넓이를 구한다.
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(!visited[i][j] && arr[i][j] == 0) {
int areaCnt = bfs(i, j);
areaCnts.add(areaCnt);
}
}
}
// 영역별 넓이를 담은 List의 size가 총 영역의 개수가 된다.
totalCnt = areaCnts.size();
// 문제 요구사항을 맞추기 위해 List 오름차순 정렬
Collections.sort(areaCnts);
bw.write(totalCnt+"\n");
for(int areaCnt : areaCnts) {
bw.write(areaCnt + " ");
}
bw.write("\n");
}
}
/**
* BFS 함수
* x,y 값을 담은 Node 클래스를 큐에 삽입해가며 너비우선탐색을 진행
* 함수 내에서 영역별 넓이를 계산하여 반환
*/
public static int bfs(int x, int y) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(x, y));
visited[x][y] = true;
// 영역별 넓이를 구하기 위한 변수
int areaCnt = 1;
while(!q.isEmpty()) {
Node now = q.poll();
for(int dir=0; dir<4; dir++) {
int i = now.getX() + dx[dir];
int j = now.getY() + dy[dir];
if(isRange(i, j)) {
if(!visited[i][j] && arr[i][j] != 1) {
visited[i][j] = true;
q.offer(new Node(i, j));
areaCnt++;
}
}
}
}
return areaCnt;
}
public static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<N && y<M) {
return true;
}
return false;
}
}
// x,y 좌표를 담을 Node 클래스
class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.