알고리즘 스터디 - 백준 2583번 : 영역 구하기

문제 해석

1. M(세로) x N(가로) 크기의 모눈종이 모두 1이상 100이하
2. K는 좌표 위에 그려지는 직사각형의 개수
3. 0 2 4 4는 (0, 2)와 (4, 4)로 만들어지는 직사각형
4. 이러한 좌표가 K개 입력하게 됨
5. 나누어지는 영역의 개수와 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력

어떤 알고리즘을 이용해야할까?

만약 우리가 (0, 0)에서 상하좌우로 움직여서 직사각형 안에 들어가지 않는 좌표를 구한다고 가정해보자. 그리고 우리가 방문한 곳을 체크하게 된다. 체크하고 난 다음, 전체 MxN 안쪽에서 우리가 가지 못했던 공간과 방문할 수 없는 곳이 구분이 될 것이다. 그러면 가지 못한 곳을 또 가서 거기서 상하 좌우로 움직이면 될 것이다.

• 우리가 갈 수 있는 곳이 막혔다는 것은 어떤 걸까? 상하좌우로 움직였을 때 이미 방문했고 갈 수 없는 곳이다.
• 그래프 알고리즘으로 구한다면 막히지 않을 때까지 최대로 갈 수 있는 넓이로 모든 정점을 방문하는 DFS나 BFS로 할 수 있다. 저번에는 DFS를 했으니 BFS로 해보겠다.

M, N, K 를 입력받음
M과 N으로 이루어진 2차 행렬 선언

K개의 좌표를 입력받음
입력 받은 좌표를 토대로 직사각형이 그려진 칸은 1로 선언하거나 못감
예를 들어, 0 2 4 4이면 x가 0이상 4미만이고 y가 2이상 4미만인 좌표들은 1로 선언하거나 못감

넓이 저장 배열 선언

dfs 알고리즘을 적용
0, 0 부터 시작해서 먼저 1이 아닌 경우
그 지점부터 시작하여 상하좌우로 움직여 넓이를 체크하고 방문했다고 체크함
0이 아닌 지점이 나올 때까지 반복 0이 아닌 지점이 없을 경우 넓이를 저장

전체를 탐색해서 모두 방문했을 경우 넓이 배열의 길이와 넓이를 오름차순으로 출력

알고리즘 코드

from collections import deque

# m, n, k를 입력 받음
# m은 y좌표 n은 x 좌표
m, n, k = map(int, input().split())

# m과 n으로 이루어진 2차 행렬 선언
m_n_list = [[0 for _ in range(n)] for _ in range(m)]

# 0 2 4 4 이면 (0, 2)와 (4, 4)로 이루어진 직사각형에는 못들어감
# 2차 배열 리스트에서 x는 0, 1, 2, 3, y는 2, 3인 조합에는 미리 방문한 곳이라고 체크함
for _ in range(k):
    x0, y0, x1, y1 = map(int, input().split())
    for i in range(y0, y1):
        for j in range(x0, x1):
            if m_n_list[i][j] == 0:
                m_n_list[i][j] = 1

# 넓이 저장 배열 선언
width = []

# bfs 선언
def bfs(x, y):
    # 상하좌우에 필요한 좌표
    dx = [0, 0, 1, -1]
    dy = [-1, 1, 0, 0]

    # 초기 넓이 선언
    initial_width = 0

    # 큐 선언
    q = []

    # 초기 좌표 삽입
    q.append((x, y))

    # 초기 좌표 방문한 것으로 바꾸고 넓이 더함
    m_n_list[y][x] = 1
    initial_width += 1

    while q:
        x_, y_ = q.pop(0)

        for i in range(4):
            new_x_ = x_ + dx[i]
            new_y_ = y_ + dy[i]
            if 0 <= new_x_ < n and 0 <= new_y_ < m and m_n_list[new_y_][new_x_] == 0:
                m_n_list[new_y_][new_x_] = 1
                initial_width += 1
                q.append((new_x_, new_y_))
    
    return initial_width

# 모든 좌표를 확인하며 필요한 것만 bfs 실행
for i in range(m):
    for j in range(n):
        if m_n_list[i][j] == 0 and 0 <= j < n and 0 <= i < m:
            width.append(bfs(j, i))

# 오름차순으로 정렬하고 출력하기
width.sort()
print(len(width))
print(*width)