백준 2583 영역 구하기

 

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

2583번: 영역 구하기

 

복잡해 보이는 것 같지만, 사실 이전에 풀어봤던 안전영역과 유기농 배추 등등,, 의 기본 그래프 탐색 문제와 비슷하다

근데 좀 오래 걸렸는데 변명 아닌 변명을 좀 해보자면..

1. 문제에서 좌표를 주길래 2차원 배열을 만들 때, 행과 열에 주어진 m, n에 각각 + 1 을 했음

2. 하지만 만든 배열의 인덱스만 사용해도 되는 문제였다,, 좌표가 아닌 영역을 묻는 문제이기 때문에 

위 2개의 실수를 깨닫는데 좀 시간이 걸렸다 앞으론 이러면 안된다..😂

📌 해결 순서

우선 주어진 영역을 색칠해야 하는데, 색칠이 안된 부분 0, 된 부분 1로 표시했다.

어차피 색칠이기 때문에 작은 직사각형들이 겹쳐도 그냥 1로 해주면 된다 

색칠이 끝나고 나면, 그래프를 돌면서 색칠 안된 부분들의 영역을 bfs로 구하는 식으로 풀었다.

파이썬 main 함수 만드는게 얼마 차이는 안나지만 메모리를 더 적게 사용하길래 main 함수 이용 풀이를 기록한다

 

📌 코드

from collections import deque
import sys

input = sys.stdin.readline


def bfs(i, j, cnt):
    que = deque()
    que.append((i, j))
    table[i][j] = 1

    while que:
        x, y = que.popleft()
        for i in range(4):
            new_x = x + dx[i]
            new_y = y + dy[i]

            if (0 <= new_x < m) and (0 <= new_y < n):
                if table[new_x][new_y] == 0:
                    table[new_x][new_y] = 1
                    cnt += 1
                    que.append((new_x, new_y))

    return cnt


if __name__ == "__main__":
    m, n, k = map(int, input().split())
    table = [[0] * (n) for _ in range(m)]
    rects = [list(map(int, input().split())) for _ in range(k)]
    areas_cnt = 0
    areas = []

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for rect in rects:
        y1, x1, y2, x2 = rect[0], rect[1], rect[2], rect[3]
        for x in range(x1, x2):
            for y in range(y1, y2):
                table[x][y] = 1

    for i in range(m):
        for j in range(n):
            if table[i][j] == 0:
                areas_cnt += 1
                area = bfs(i, j, 1)
                areas.append(area)

    print(areas_cnt)
    areas.sort()
    for area in areas:
        print(area, end=" ")