Yong's Tech Story

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

문제 풀이 (JAVA) 

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[][] arr; // 이차원 배열
	static int totalCnt; // 영역의 총 개수
	static boolean[][] visited; // 방문 여부 배열
	static int size = 0; // 영역의 넓이
	static int[] dx = { 1, 0, -1, 0 }; // 4방향 
	static int[] dy = { 0, 1, 0, -1 }; 
	static int M; // 행 개수
	static int N; // 열 개수

	public static void main(String[] args) throws IOException {
		// 영역 구하기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());// 행 개수
		N = Integer.parseInt(st.nextToken());// 열 개수
		int K = Integer.parseInt(st.nextToken());// 입력 줄

		arr = new int[M][N];
		visited = new boolean[M][N];

		List<Integer> list = new ArrayList<>(); // 영역 넓이 저장 리스트

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());

			int lx = Integer.parseInt(st.nextToken()); // 왼쪽 꼭짓점 X
			int ly = Integer.parseInt(st.nextToken()); // 왼쪽 꼭짓점 Y
			int rx = Integer.parseInt(st.nextToken()); // 오른쪽 꼭짓점 X
			int ry = Integer.parseInt(st.nextToken()); // 오른쪽 꼭짓점 Y
			
            for (int x = ly; x < ry; x++) { // 배열의 x는 꼭짓점 Y
				for (int y = lx; y < rx; y++) { // 배열의 y는 꼭짓점 X
					arr[x][y] = 1; // 색칠 된 도형의 경우 1로 선언
				}
			}
		}

		for (int x = 0; x < M; x++) {
			for (int y = 0; y < N; y++) {
  				// dfs에서 연결 되지 않은 0으로 x,y를 탐색한다.
				if (visited[x][y] == false && arr[x][y] == 0) {
					size = 1; // 현재 위치 사이즈 ==1 로 초기화
					visited[x][y] = true;
					totalCnt++; // if조건에 걸렸을때 하나의 영역의 시작이다.
					dfs(x, y);

					list.add(size); // dfs 종료 시 계산된 사이즈 추가
				}
			}
		}

		Collections.sort(list); // 오름차순 정렬

		System.out.println(totalCnt);
		for (Integer n : list) {
			System.out.print(n + " ");
		}
	}

	private static void dfs(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i]; // 다음 탐색할 X
			int ny = y + dy[i]; // 다음 탐색할 Y
			if (nx >= 0 && nx < M && ny >= 0 && ny < N && visited[nx][ny] == false && arr[nx][ny] == 0) {
				visited[nx][ny] = true;
				size++;
				dfs(nx, ny);
			}
		}
	}

}

문제 풀이

1. 해당 문제는 영역을 구하는 문제로 색칠된 도형의 넓이가 아닌 색칠하지 않은 도형의 넓이를 구하는 문제이다.

2. 문제에서 제시 되는 꼭짓점의 도형맵을 아래로 뒤집게 되면, 입력받은 꼭짓점과 이차원 배열의 (x,y)가 일치하게 된다.

3. 단, 오른쪽 꼭짓점의 경우, 입력 꼭짓점 rx-1, ry-1까지 반복문을 계산하여 도형의 넓이를 구해야 일치한다.

4. 나머지는 기존의 dfs 공식을 사용한다.(경계값 체크 필수)

결론

: 해당 문제는 dfs를 변형한 문제로, 꼭짓점의 위치를 이차원 배열의 위치와 매핑시켜 색칠 된 도형의 넓이를 구하는 것이 핵심이다. 입력 변수를 받아 arr를 잘 입력하였다면, 기존의 dfs 공식을 써서 풀 수 있다.