[Python 파이썬] 백준 2583번 - 영역 구하기

2024년 10월 2일

문제 링크 : 백준 2583번 - 영역 구하기

 

문제

 

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

 

 

문제 접근

 

암시적 그래프가 주어지기는 하는데, 우리가 2차원 배열에서 사용하는 좌표 체계랑은 조금 다름에 유의해야 한다.

 

왼쪽 아래가 [0, 0] 이고, 오른쪽 위가 [7, 5] 이다.

우리가 2차원 배열에서 표기하는 방식은 보통 [행, 열] 이지만 이 문제에서는 [x좌표, y좌표]로 주어졌다.

 

 

[x, y] 형태의 좌표계를 [행, 열] 형태의 표현으로 바꿀 것이다(우리가 다루기 쉽게!)

 

 

시계방향으로 90도 돌리면 위와 같다.

 

이러면 입력값인 M과 N이 의미하는 바가 달라지게 된다.

 

왼쪽 위는 [0, 0] 이고 오른쪽 아래는 [7, 5] 가 된다.

 

그리고 의미하는 바가 달라진 M, N도 행과 열로 의미하면 다음과 같게 된다.

 

여기에서 우리는 좌표 형태로 보는게 아닌, 2차원 배열 형태로 행과 열을 이용해 각 좌표를 나타내고 싶으므로 다음과 같이 각 칸에 좌표를 새로 부여해야 한다. 이 과정에서 오른쪽 아래의 마지막 좌표 값이 달라지게 된다.

 

 

우리는 2차원 배열 형태로 가공한 위의 암시적 그래프를 활용해 문제를 풀 것이다.

 

우선, 입력값 M과 N이 주어졌을 때 전체 board의 사이즈는 N행 M열의 N x M 사이즈이므로 board는 다음과 같이 초기화해준다.

 

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

 

또한, K줄에 걸쳐 입력받는 데이터의 의미도 변경되어야 한다.

 

# 원래 입력받는 값
# 왼쪽 아래 x좌표, 왼쪽 아래 y좌표, 오른쪽 위 x좌표, 오른쪽 위 y좌표
x1, y1, x2, y2

 

하지만 board를 시계방향으로 90도 회전시킨 과정에서 x와 y 입력값의 의미가 서로 바뀌었기에 이를 고려해주어 헷깔리지 않게 하였다.

 

# 변경된 의미를 고려하여 변수명에 반영
# 왼쪽 위 y좌표, 왼쪽 위 x좌표, 오른쪽 아래 y좌표, 오른쪽 아래 x좌표
y1, x1, y2, x2 = map(int, input().split())

 

왼쪽 위 좌표를 기준으로 한 행씩 직사각형 영역 칠해준다. 해당 작업을 수행해주는 로직은 아래의 코드와 같다.

 

for _ in range(K):
    y1, x1, y2, x2 = map(int, input().split())
    now_row = y1
    for row in range(y2 - y1):
        now_col = x1
        for col in range(x2 - x1):
            board[now_row][now_col] = 1
            now_col += 1
        now_row += 1

 

이후 작업은 동일하다.

 

board의 모든 행과 열을 순회하며 직사각형 영역으로 칠해지지 않은, 즉 board에서 0인 좌표를 찾았다면 해당 지점을 시작점으로 두고 너비 우선 탐색을 진행한다.

( 그래프 탐색 이론 : 너비 우선 탐색과 깊이 우선 탐색이란? )

[알고리즘] 깊이우선탐색(DFS), 너비우선탐색(BFS) [ 백준 1260번 - DFS와 BFS ]

 

너비 우선 탐색을 진행한 횟수가 곧 문제에서 원하는 영역의 개수이며, 각 영역을 탐색하여 해당 영역의 넓이를 오름차순으로 출력해주면 된다.

 

---

입력 예제

 

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

 

 

 

출력 예제

 

3
1 7 13

 

---

전체 코드

 

import sys
from collections import deque
input = sys.stdin.readline

def bfs(start_row, start_col):
    cnt = 0
    queue = deque()

    queue.append([start_row, start_col])
    board[start_row][start_col] = 1
    cnt += 1

    # 동, 남, 서, 북
    d_row = [0, 1, 0, -1]
    d_col = [1, 0, -1, 0]

    while queue:
        now_row, now_col = queue.popleft()
        for i in range(4):
            next_row, next_col = now_row + d_row[i], now_col + d_col[i]
            if 0 <= next_row < N and 0 <= next_col < M:
                if board[next_row][next_col] == 0:
                    board[next_row][next_col] = 1
                    queue.append([next_row, next_col])
                    cnt += 1
    
    return cnt


def solution():
    result = []

    for row in range(N):
        for col in range(M):
            if board[row][col] == 0:
                result.append(bfs(row, col))
    print(len(result))
    print(*(sorted(result)))


if __name__ == "__main__":
    M, N, K = map(int, input().split())

    # 2차원 배열에서는 왼쪽 위가 [0, 0] 이지만, 문제에서는 왼쪽 아래가 [0, 0] 이다.
    # board를 시계방향으로 90도 회전시켜 풀어도 문제 해결에 지장을 주지 않는다고 판단
    board = [[0 for _ in range(M)] for _ in range(N)]

    for _ in range(K):
        y1, x1, y2, x2 = map(int, input().split())
        now_row = y1
        for row in range(y2 - y1):
            now_col = x1
            for col in range(x2 - x1):
                board[now_row][now_col] = 1
                now_col += 1
            now_row += 1
    
    solution()

 

 

---

풀이 후기

 

문제에서 주어진 좌표를 2차원 배열에서 인덱스를 다루는 형태로 변환하는 과정에서 시간을 많이 투자했다.

주어진 데이터를 내가 다루기 쉽게 가공할 수만 있다면, 오히려 문제 풀이에 더욱 효율적이라고 생각한다.