이미지를 누르면 문제로 이동합니다.

문제 : 영역 구하기

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

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

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

import sys
sys.stdin = open('input.txt')
from pprint import pprint
sys.setrecursionlimit(10**6)
M, N, Sqs = map(int, input().split())

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

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


def dfs(y, x):
    global cnt
    board[y][x] = 1
    cnt += 1

    for i in range(4):
        new_y = y + dy[i]
        new_x = x + dx[i]
        if 0 <= new_y <= M-1 and 0 <= new_x <= N-1:
            if board[new_y][new_x] == 0:
                dfs(new_y, new_x)



for i in range(Sqs):
    lx, ly, rx, ry = map(int, input().split())
    for i in range(lx, rx):
        for j in range(ly, ry):
            board[j][i] = 1

result = []
for i in range(M):
    for j in range(N):
        if board[i][j] == 0:
            cnt = 0
            dfs(i, j)
            result.append(cnt)
print(len(result))
for x in sorted(result):
    print(x, end=' ')

기본적인 dfs문제로, N * M 형태의 list의 각 인자에 0을 저장하고, 주어진 input좌표를 해당 리스트의 격자 좌표로 변환하여 1로 변환하면 기본board가 만들어진다.

이후 dfs방식을 이용하여 각 구획마다 0을 만날 때마다 cnt(넓이)를 1을 더한 후, 방문의 의미로 해당 좌표의 board값을 1로 설정한다.

모든 좌표에 대해서 dfs를 수행하면 각 구획마다의 넓이 구할 수 있다.
중요한 것은 dfs자체보다 input으로 주어진 각 좌표를 내가 만든 board의 격자 내의 좌표로 치환하는 과정이다.