https://www.acmicpc.net/problem/2583
2583번: 영역 구하기
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오
www.acmicpc.net
걸린 시간 : 47분 8초 (자바 미숙)
자바로 코테가 미숙해서 열심히 푸는 중...!! 자바 언어에 익숙해지고자 풀어봤다.
문제에서 입력할 때 M, N 순서로 주기도 하고 N, M 순서로 주기도 해서 주의해야 한다.
알고리즘
영역이 100 X 100 이하이므로 이 크기의 2차원 배열을 만들어 입력 받을 때 칠해진 곳을 체크한다.
그 후 DFS로 방문체크를 하며 연결요소의 수를 세면 된다. BFS도 가능하지만, 재귀가 가능한 DFS가 구현이 더 쉽다.
정답 코드
import java.io.*;
import java.util.*;
public class BOJ2583 {
static boolean[][] board = new boolean[101][101];
static boolean[][] vis = new boolean[101][101];
static int[] di = {-1, 0, 0, 1};
static int[] dj = {0, -1, 1, 0};
static int M, N, K;
static List<Integer> area = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s = bf.readLine();
String[] tmp = s.split(" ");
M = Integer.parseInt(tmp[0]);
N = Integer.parseInt(tmp[1]);
K = Integer.parseInt(tmp[2]);
while (K-- > 0) {
s = bf.readLine();
StringTokenizer st = new StringTokenizer(s);
int j1 = Integer.parseInt(st.nextToken());
int i1 = Integer.parseInt(st.nextToken());
int j2 = Integer.parseInt(st.nextToken());
int i2 = Integer.parseInt(st.nextToken());
for (int i = i1; i < i2; i++) {
for (int j = j1; j < j2; j++) {
board[i][j] = true;
}
}
}
int answer = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (!vis[i][j] && !board[i][j]) {
answer++;
area.add(dfs(i ,j));
}
}
}
System.out.println(answer);
Collections.sort(area);
for (int a : area) {
System.out.print(a + " ");
}
}
static int dfs (int ci, int cj) {
vis[ci][cj] = true;
int ret = 1;
for (int k = 0; k < 4; k++) {
int ni = ci + di[k];
int nj = cj + dj[k];
if (ni < 0 || ni >= M || nj < 0 || nj >= N || vis[ni][nj] || board[ni][nj]) continue;
ret += dfs(ni, nj);
}
return ret;
}
}
'Baekjoon Online Judge' 카테고리의 다른 글
[BOJ] 1744 : 수 묶기 (Java) (1) | 2023.10.26 |
---|---|
[BOJ] 21608 : 상어 초등학교 (Java) with 정렬 (1) | 2023.10.26 |
[BOJ] 1941: 소문난 칠공주 (Java) with 조합 (0) | 2023.10.19 |
[BOJ] 1520 : 내리막 길 (C++) with Top Down DP (1) | 2023.10.05 |
[BOJ] 11404 : 플로이드 (C++) with 플로이드 (1) | 2023.10.04 |