[BAEKJOON]2583 영역 구하기

문제 요약

• 알고리즘 분류: bfs, 구현, 시물레이션
• 난이도:Silver1
• 문제내용:
  • 사가형이 가로, 세로 길이와 색칠한 범위가 주어진다.
  • 색칠하지 않은 구역개수와 각 구역의 넓이를 오름차순으로 출력해라
• 사이트: https://www.acmicpc.net/problem/2583
  .

2583번: 영역 구하기

문제풀이

 이번 문제는 DFS,BFS 탐색 문제이다. DFS로 풀수있지만 BFS가 DFS보다 속도가 더 빨라서 이번 문제는 BFS로 푸는게 좋다.  BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다.

 기존 BFS는 각 노드간의 탐색인데 이번에는 2차원 배열로 응용한 BFS 탐색이다. 노드 대신 2차원 배열로 변경 된것만 생각하면 된다.

문제 접근 방법

 이번 문제의 주는 BFS + 시물레이션 2개를 구현 해야 한다. 일단 시물레이션은 어떻게 구현 해야 하는지 부터 봐야 한다.

일단 (0, 0) 부터 시작해서 (N, M)까지 탐색하면서 빈곳을 찾는다. 빈 곳을 찾으면 빈 곳 부터 시작해서 색칠한 영역을 칠하면서 색칠한 개수 만큼 추가를 시켜주면 끝이다.

 위 그림 을 보면 빈곳 (x ,y) 위치를 찾았다고 가정하면 (x, y)좌표 부터 시작해서 상하좌우로 탐색해서 빈 역역을 색칠하고 색칠한 개수를 배열이나 리스트에 추가만 해주기만 하면된다.

정리

1. (0, 0)부터 (M, M)까지 탐색을 하면서 빈 영역을 구한다.
2. 빈 영역을 구했으면 bfs 알고리즘으로 상하좌우 탐색하면서 빈 영역을 색칠하고 색칠한 개수만큼 추가한다.

Code

python

import sys
from collections import deque
input = sys.stdin.readline
# 상하좌우 이동 좌표
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# bfs 탐색으로 영역을 색칠하고 색칠한 개수를 반환한다.
def bfs(x, y):
    queue = deque([(x, y)])
    count = 1
    paper[x][y] = 1
    while queue:
        cx, cy = queue.popleft()
        #상하 좌우 탐색
        for i in range(4):
            fx, fy = cx + dx[i], cy + dy[i]
            # 빈영역 있으면 색칠하고 q에 추가한다.
            if(0<= fx < N and 0<= fy < M and paper[fx][fy] == 0):
                paper[fx][fy] = 1
                count += 1
                queue.append((fx, fy))
    return count

M, N, K = map(int, input().split())

paper = [[0] * M for _ in range(N)]

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    # 색칠하기
    for i in range(x1, x2):
        for j in range(y1, y2):
            paper[i][j] = 1

areas = []
for x in range(N):
    for y in range(M):
    	# 빈곳을 찾았으면 빈 영역의 개수를 추가한다.
        if(paper[x][y] == 0):
            areas.append(bfs(x, y))

areas.sort() # 오른 차순 정렬
print(len(areas))
print(' '.join(map(str, areas)))

Java

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

public class Main {
	
	static int[][] paper;
	static int N, M;
	
	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());
		paper = new int[N][M];
		int x1, y1, x2, y2;
		for(int k = 0; k < K; k++) {
			st = new StringTokenizer(br.readLine());
			x1 = Integer.parseInt(st.nextToken());
			y1 = Integer.parseInt(st.nextToken());
			x2 = Integer.parseInt(st.nextToken());
			y2 = Integer.parseInt(st.nextToken());
            // 색칠하기
			for(int x = x1; x < x2; x++) {
				for(int y = y1; y < y2; y++) {
					paper[x][y] = 1;
				}
			}
		}
		
		List<Integer> areas = new ArrayList<Integer>();
		for(int x = 0; x < N; x++) {
			for(int y = 0; y < M; y++) {
            	// 빈곳을 찾았으면 빈 영역의 넓이를 추가한다.
				if(paper[x][y] == 0) {
					areas.add(bfs(x, y));
				}
			}
			
		}
		Collections.sort(areas); # 오름차순으로 정렬
		System.out.println(areas.size());
		for(int i = 0; i < areas.size(); i++) {
			System.out.print(areas.get(i) + " ");
		}
		
	}
	
    // bfs탐색후 빈 영역의 개수를 반환한다.
	public static int bfs(int x, int y) {
		// 상화좌우 방향
		int[] dx = new int[] {0, 0, -1, 1};
		int[] dy = new int[] {-1, 1, 0, 0};
		
		Queue<int[]> queue = new LinkedList<int[]>();
		int count = 1;
		paper[x][y] = 1;
			
		queue.add(new int[] {x, y});
		int fx, fy, cx, cy;
		while (!queue.isEmpty()) {
			int[] location = queue.poll();
			cx = location[0];
			cy = location[1];
            // 상하좌우 탐색하면서 빈 영역을 찾는다.
			for(int i = 0; i < 4; i++) {
				fx = cx + dx[i];
				fy = cy + dy[i];
                // 비어 있으면 색칠하고 개수와 큐에 추가한다.
				if(0 <= fx && fx < N && 0<= fy && fy < M && paper[fx][fy] == 0) {
					paper[fx][fy] = 1;
					queue.add(new int[] {fx, fy});
					count++;
				}
			}
		}
		
		return count;
	}
	
}