[백준] 2583번 : 영역구하기 - JAVA

SUBNY·2023년 8월 21일

Java 백준 알고리즘 코딩테스트

백준

목록 보기

17/22

(https://www.acmicpc.net/problem/2583)

접근 방법 🧐

이전에 DFS로 풀었던 단지번호 붙이기 문제가 생각났다. 그 문제에서는 아파트가 있는 것들을 세서 단지 번호를 붙여줬지만, 이번에는 아파트가 없는 것들을 세서 붙여줘야겠다고 생각했다.

단지번호붙이기

다른 점이 있다면, (x1,y1) 과 (x2, y2) 좌표를 줘서 그것으로 내가 땅따먹기 마냥 색을 칠해줘야한다는 것.

분리된 영역이 몇 개가 나올지 모르니 result라는 ArrayList 선언

(x1,y1) (x2,y2) 좌표를 입력 받고 해당 영역에 포함된 칸들을 바로 1로 초기화 시켜준다.

0이면 dfs 들어가니 크기를 담는 변수인 size는 1로 초기화

방향배열로 탐색하며 dfs진행

내가 쓴 코드 ✍️

import java.util.*;
import java.io.*;

public class Main {
	
	static int M, N, K;
	static int[][] ddang;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	static int size;
	static ArrayList<Integer> result;
	public static void main(String[] args) throws IOException{
		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()); //y축
		N = Integer.parseInt(st.nextToken()); //x축
		K = Integer.parseInt(st.nextToken());
		
		ddang = new int[M][N]; //행(y인 M) 열(y인 N)
		result = new ArrayList<>();
		
		for(int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			for(int y=y1;y<y2;y++) {
				for(int x=x1;x<x2;x++) {
					ddang[y][x] = 1; //한칸씩 색칠해준다
				}
			}
		}
		
		for(int i=0;i<M;i++) {
			for(int j=0;j<N;j++) {
				if(ddang[i][j] == 0) {
					size=1;
					dfs(i, j);
					result.add(size);
				}
			}
		}
		
		Collections.sort(result);
		
		StringBuilder sb = new StringBuilder();
		
		sb.append(result.size()+"\n");
		for(int r : result) {
			sb.append(r+" ");
		}
		bw.write(sb+"");
		bw.flush();
		bw.close();
	}
	
	public static void dfs(int y, int x) {
		ddang[y][x] = 1; //visited를 따로 만들어주지 않고, 들어왔음을 1로 표시했다.
		
		for(int i=0;i<4;i++) {
			int nx = dx[i]+x;
			int ny = dy[i]+y;
			
			if(nx>=0 && ny >=0 && nx<N && ny<M && ddang[ny][nx]==0) {
				size++;
				dfs(ny,nx);
			}
		}
	}
}