[백준 2583] 영역 구하기

www.acmicpc.net/problem/2583

2583번: 영역 구하기

---

접근

사각형을 제외한 부분의 개수와 그 영역의 칸 수를 구해야한다.

먼저 이차원 리스트에 직사각형 부분의 좌표에 0이 아닌 수로 표시를 한다. 이렇게되면 0인 부분이 구해야하는 영역이된다.

이후 2차원 리스트를 탐색하여 0을 만날 때마다 BFS 또는 DFS로 탐색을 하고 각 칸의 수를 기록한다.

 

구현

graph라는 2차원 리스트에 직사각형을 표시한다.

문제에서 주어지는 예시그림에서 상하반전된 그림이 될 것이다.

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

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for y in range(y1, y2):
        for x in range(x1, x2):
            graph[y][x] += 1

 

이제 2차원 리스트를 탐색하면서 0을 만날 때는 영역이 발견되었다는 의미이기 때문에 BFS 탐색을 진행한다. 그리고 해당 영역의 개수를 구해야하기 때문에 1을 집어넣는다.

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

 

BFS 탐색을 진행하면서 해당 칸의 상하좌우가 0이거나 범위 내에 있다면 방문표시를 하고 칸 수를 증가시킨다.

def bfs(y, x):
    q = deque()
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    q.append((y, x))

    while q:
        cy, cx = q.popleft()

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and graph[ny][nx] == 0:
                graph[ny][nx] = 1
                size_list[answer-1] += 1
                q.append((ny, nx))

 

최종적으로 영역의 개수와 각 영역의 칸 수를 오름차순으로 출력한다.

---

전체 코드

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


def check_range(y, x):
    return (y>=0 and y<M) and (x>=0 and x<N)

def bfs(y, x):
    q = deque()
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    q.append((y, x))

    while q:
        cy, cx = q.popleft()

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and graph[ny][nx] == 0:
                graph[ny][nx] = 1
                size_list[answer-1] += 1
                q.append((ny, nx))

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

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for y in range(y1, y2):
        for x in range(x1, x2):
            graph[y][x] += 1

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

size_list = sorted(size_list)
print(answer)
print(*size_list)