코드

import sys
sys.setrecursionlimit(10**9)

m, n, k = map(int, input().split())

# 모눈종이를 모두 0으로 초기화
graph = [[0 for _ in range(n)] for _ in range(m)]

# 주어지는 4개의 좌표를 통해
# K개의 직사각형을 그림
# => 해당 좌표를 1로 바꿈
# 이때, 그려지는 그래프는 문제에서의 그림이 상하 반전이된 상태로 생성됨
# 단순 영역의 개수와 넓이(눈금의 간격 1이므로 넓이도 1)를 구하는 문제이므로 굳이 신경쓸 필요없음
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1
    
# 영역의 넓이를 담을 변수
# 눈금의 간격이 1이므로 넓이도 한 칸이 늘어나면 1씩 증가
cnt = 0
def dfs(y, x):
    global cnt
    
    # 방문한 지점은 2로 변경 (0만 아니면 됨)
    graph[y][x] = 2
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 방문했으므로 넓이 +1
    cnt += 1
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        
        # 다음 구역도 0이면 dfs 수행
        if graph[ny][nx] == 0:
            dfs(ny, nx)

    # 최종 넓이 반환
    return cnt

# 영역 별 넓이를 담을 리스트
result = []
            
for i in range(m):
    for j in range(n):
        
        # 주어진 모눈종이가 직사각형이 덮어지지 않은 부분만 dfs를 수행
        if graph[i][j] == 0:
            
            # 매 반복마다 cnt를 초기화시켜야
            # 영역 별로 다른 cnt를 구할 수 있음
            cnt = 0
            
            # 반환되는 cnt를 result에 저장
            result.append(dfs(i, j))
            
# 오름 차순으로 정렬하라 했음
result.sort()

# 영역의 개수
print(len(result))

# 영역별 넓이
print(*result)

문제 해설

DFS와 BFS를 활용하여 풀 수 있는 문제.

이 문제의 경우, 기본적으로 DFS와 BFS를 활용할 수만 있다면 쉽게 풀 수 있는 문제여서 설명은 주석으로 대신하지만, 한 가지 주의해야 하는 부분이 있어 이 부분만큼은 짚고 기록해야겠다.

이 문제는 그래프에서 직사각형이 차지하는 부분을 제외한 나머지 영역에 대하여, 나머지 영역의 개수와 각각의 넓이를 구하라는 문제이다. 즉, 흔히 접하게 되는 문제와 달리 그래프 자체를 주는 것이 아니라 직사각형이 놓이는 곳을 좌표점(이 문제에서 좌표는 사각형 모눈종이 한 칸의 구석)으로 표현하여 문제를 제시하였다. 이 부분이 처음에 나를 어지럽게 만들었다.

이 좌표를 어떻게 흔히 접한 그래프의 모양으로 나타낼 수 있을까?

이는 생각보다 간단하였다. k개 주어진 좌표 영역들을 그냥 고스란히 그래프에 1로 덮어버리면 우리가 항상 접하는 그래프 모양과 매우 유사하게 표현할 수 있었다. 단, 문제에서 예시로 들어준 모눈종이의 모양과 상하가 반전된 채로 그려지는데, 이는 영역의 개수와 영역의 넓이를 구하는데에는 아무런 제약이 없다!!

만약 제약이 있는 경우라면 다른 방법을 사용해야겠지만, 이 문제의 경우에는 그냥 주어진 좌표를 우리가 흔히 쓰는 그래프를 만드는 방식에 적용하여도 문제를 풀 수 있었다.

평소에 접하지 않는 방식의 문제이다보니, 알고리즘 구현 자체는 어렵지 않으나 문제 풀이 방식에 대한 새로운 접근이 필요한 문제였다. 매번 느끼는 점이지만, 정말 다양한 문제를 많이 풀어봐야겠다ㅜㅜ.

댓글남기기

참고