S1 2583. 영역 구하기

문제 보기 :  2583번: 영역 구하기

---

문제

• 정답률 : 57%

---

작성 코드

# n: 세로 크기, m: 가로 크기, t: 직사각형 개수 입력받기
n, m, t = map(int, input().split())

# arr: 방문 여부를 저장하는 2차원 배열 초기화
arr = [[False] * m for _ in range(n)]

# t개의 직사각형 좌표를 입력받아 해당 영역을 True로 설정
for _ in range(t):
    a1, b1, a2, b2 = map(int, input().split())
    for y in range(a1, a2):  # x 좌표 범위
        for x in range(n - b2, n - b1):  # y 좌표 범위 (상하 뒤집힘 처리)
            arr[x][y] = True

# 연결된 영역의 크기를 저장할 리스트
answer = []

# 상하좌우 방향 이동을 정의
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 특정 시작점에서 연결된 영역 크기를 계산하는 함수
def area(arr, start): 
    count = 1
    arr[start[0]][start[1]] = True  # 방문 처리
    dd = deque([start])  # BFS 큐 초기화
    while dd:
        x, y = dd.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            # 배열 범위 내에서 방문하지 않은 칸이면 추가 탐색
            if 0 <= nx < n and 0 <= ny < m and not arr[nx][ny]:
                count += 1
                arr[nx][ny] = True  # 방문 처리
                dd.append((nx, ny))
    return count

# 모든 칸을 순회하며 방문하지 않은 칸에서 영역 계산
for a in range(n):
    for b in range(m):
        if not arr[a][b]:
            answer.append(area(arr, (a, b)))

# 결과를 오름차순으로 정렬하여 출력
answer.sort()
print(len(answer))  # 영역의 개수 출력
print(*answer, sep=' ')  # 각 영역의 크기 출력

---

풀이

1. 직사각형 영역의 크기 n, m과 직사각형 개수 t를 입력받는다.

2. False로 초기화된 2차원 배열을 생성하여, 직사각형 영역을 True로 표시한다.

3. 상하좌우로 이동할 수 있도록 방향 배열을 정의한다.

4. BFS를 통해 방문하지 않은 칸에서 연결된 영역의 크기를 계산한다.

5. 모든 칸을 순회하며 새롭게 발견한 영역은 크기를 리스트에 추가한다.

6. 영역 크기를 정렬한 뒤, 영역 개수와 크기를 출력한다.