[백준(BOJ)] 2583번 : 영역 구하기 - PYTHON[파이썬]

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

2583번: 영역 구하기

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

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

 

---

 

⊙ 문제 접근 과정

 

먼저 0으로 초기화된 배열을 생성해준다.

그리고 직사각형이 포함된 영역에 대해 1을 더해준다.

 

그러면 0의 값을 가진 좌표에 대해 bfs를 돌려주면 된다.

 

마지막으로 결과를 출력해줄때에는 오름차순 정렬을 하여 크기 순으로 차례차례 출력해준다.

 

 

---

 

⊙ 문제 풀이

 

from collections import deque

M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]


def bfs(i, j):
    q = deque()
    q.append((i, j))
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    cnt = 1
    while q:
        y, x = q.popleft()
        for k in range(4):
            ny = y+dy[k]
            nx = x+dx[k]
            if (0 <= ny < M) and (0 <= nx < N) and graph[ny][nx] == 0:
                graph[ny][nx] = 1
                q.append((ny, nx))
                cnt += 1
    return cnt


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

result = []

for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            graph[i][j] += 1
            result.append(bfs(i, j))

print(len(result))
print(*sorted(result))

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!