https://www.acmicpc.net/problem/2583
분류 : DFS, BFS
더보기
public class Main {
static Myscanner sc = new Myscanner();
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static int paper[][], M, N, K,color;
static int visited[][];
public static void main(String[] args) {
M = sc.nextInt();
N = sc.nextInt();
K = sc.nextInt();
paper = new int[M][N];
visited = new int[M][N];
int result[] = new int[100*100+1];
for (int tc = 0; tc < K; tc++) {
int y1 = sc.nextInt();
int x1 = sc.nextInt();
int y2 = sc.nextInt();
int x2 = sc.nextInt();
for (int x = x1; x < x2; x++) {
for (int y = y1; y < y2; y++) {
paper[x][y] = 1;
}
}
}
color =0;
for (int x = 0; x < M; x++) {
for (int y = 0; y < N; y++) {
if (paper[x][y] == 0 && visited[x][y] == 0) {
color++;
DFS(x,y);
}
}
}
for (int x = 0; x < M; x++) {
for (int y = 0; y < N; y++) {
if(visited[x][y]!=0) result[visited[x][y]]++;
}
}
Arrays.sort(result);
out.println(color);
for(int idx =0; idx<result.length;idx++){
if(result[idx]!=0){
out.print(result[idx]+" ");
}
}
out.close();
}
private static void DFS(int x, int y) {
if(x<0 || x>=M || y<0 || y>=N || paper[x][y]==1 || visited[x][y]!=0) return;
visited[x][y]=color;
DFS(x-1,y);
DFS(x+1,y);
DFS(x,y-1);
DFS(x,y+1);
}
}
DFS를 통해 paper [x][y] ==0 인 지점을 탐색하며 color를 칠한 후에 result 배열을 정렬 후에 값 출력하면 완료.
문제에서는 왼쪽 아래가 (0,0)이라는 점이 걸렸지만 상관없이 그냥 구해도 답은 나오는 듯하다.
'PS' 카테고리의 다른 글
[BOJ] 1987번 : 알파벳 (0) | 2017.06.10 |
---|---|
[BOJ] 2468번: 안전 영역 (0) | 2017.06.09 |
[BOJ] 11049번: 행렬 곱셈 순서 (0) | 2017.06.08 |
[BOJ] 2667번: 단지번호붙이기(DFS) (0) | 2017.06.07 |
[BOJ] 1012번 : 유기농 배추(DFS) (0) | 2017.06.07 |