알고리즘 - 영역 구하기

문제

• 링크

코드

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 Main {
	static int M, N, K, val;
	static int[][] arr, visited ;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(stk.nextToken());
		N = Integer.parseInt(stk.nextToken()); 
		K = Integer.parseInt(stk.nextToken());
		
		arr = new int[M][N];
		
		for(int i = 0 ; i < K ; i++) {
			StringTokenizer stk1 = new StringTokenizer(br.readLine());
			int lx = Integer.parseInt(stk1.nextToken());
			int ly = Integer.parseInt(stk1.nextToken());
			int rx = Integer.parseInt(stk1.nextToken());
			
			int ry = Integer.parseInt(stk1.nextToken());
			
			for(int j = ly; j < ry ; j++) {				
				for(int k = lx; k < rx ; k++) {
					arr[j][k] = -1;
				}
			}
		
		}
//		System.out.println(Arrays.deepToString(arr));
		visited = new int[M][N];
		int count = 0; 
		List<Integer> list = new ArrayList<>();
		StringBuffer stb = new StringBuffer();
		for(int i = 0 ; i < M ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(visited[i][j] == 0 && arr[i][j]!=-1) {
					val = 1;
//					System.out.println(i+","+j);
//					System.out.println();
					dfs(i,j);
					list.add(val);
					count++;
					val = 1;
				}
			}			
		}
		System.out.println(count);
		Collections.sort(list);	
		for(int i = 0; i < count ; i++) {
			stb.append(list.get(i)+" ");
		}
		stb.setLength(stb.length()-1);
		System.out.println(stb);
		
		
	}
	private static int dfs(int i, int j) {
		// TODO Auto-generated method stub
		if(visited[i][j] == 1) {
			return 0;
		}
		
		visited[i][j] = 1;
		
		for(int k = 0; k < 4 ; k++) {
			int nr = i + dr[k];
			int nc = j + dc[k];
			
			if(nr >= 0 && nr < M && nc >= 0 && nc < N){
				if(visited[nr][nc]==0 && arr[nr][nc]!=-1) {
					dfs(nr,nc);	
					val+=1;
				}	
			}
		}
		
		return val;
		
		
	}
}

회고

• DFS, BFS에 대한 코드 및 효율적인 코드 작성을 고민해보자

• 조금 더 간략하게 표현할 수 있을 듯 하다