백준 2583번 : 영역 구하기

 문제

www.acmicpc.net/problem/2583

2583번: 영역 구하기

2583 영역 구하기

 

 구현 방법

 해당되는 영역들을 1로 채운 다음 빈 칸을 중심으로 dfs를 통해 구현하였습니다. 

한 영역에서 탐색이 끝난 후 계산한 너비를 저장을 합니다. 

모든 영역 탐색이 끝난 뒤에 저장해 둔 너비들을 정렬 하고 출력해줍니다.

 

 구현 코드

package BOJ.Silver.bfsdfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ2583_영역구하기 {
	static int R, C, K, cnt;
	static List<Integer> ans;
	static int[][] map, deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		ans = new ArrayList<>();
		for (int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine());
			int startC = Integer.parseInt(st.nextToken());
			int startR = Integer.parseInt(st.nextToken());
			int endC = Integer.parseInt(st.nextToken());
			int endR = Integer.parseInt(st.nextToken());
			for (int r=startR; r<endR; r++) {
				for (int c=startC; c<endC; c++) {
					map[r][c] = 1;
				}
			}
		}
		
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (map[r][c]==0) {
					map[r][c] = 1;
					cnt = 0;
					dfs(r, c);
					ans.add(cnt);
				}
			}
		}
		
		Collections.sort(ans); // 넓이 정렬
		sb.append(ans.size()+"\n");
		for (int i=0;i<ans.size();i++) sb.append(ans.get(i)+" ");
		System.out.println(sb);
	}
	
	static void dfs(int r, int c) {
		cnt++; // 넓이 구하기
		for (int d=0;d<4;d++) {
			int nr = r+deltas[d][0];
			int nc = c+deltas[d][1];
			if (isIn(nr, nc) && map[nr][nc]==0) {
				map[nr][nc] = 1;
				dfs(nr, nc);
			}
		}
		return;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!