[백준] 2583 영역 구하기(python 파이썬)

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

2583번: 영역 구하기

---

그래프 탐색하는 문제. 비슷한 유형의 문제를 풀어봤으면 쉬운 문제.

---

아이디어

1. 모눈종이 

• M*N 크기의 2차원 리스트로 모눈종이를 나타냈다.
• 주어진 직사각형 좌표에 따라 직사각형을 표현해준다. 1은 직사각형, 0은 빈공간을 나타낸다.
• 문제에서는 좌표가 왼쪽 아래가 원점(0, 0)이지만, 리스트는 왼쪽 위가 원점이다.
• 어차피 가로축에 대해 대칭이므로 문제에서 요구한 값을 구하는데 문제없다고 판단해 그대로 풀었다.

2. 빈공간 개수, 넓이 구하기

• 모든 칸에 대해 dfs를 해본다.
• 선택한 칸이 0이라면 주위를 탐색해 넓이를 구하고, 개수에 +1 해준다. 
• 이미 방문한 칸은 1로 변환하여 중복을 방지해준다.

---

전체 코드

import sys
sys.setrecursionlimit(10**6)
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def dfs(x, y):
    global volume
    if x < 0 or x >= M or y < 0 or y >= N:
        return 0

    if paper[x][y] == 0:
        volume += 1
        paper[x][y] = 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            dfs(nx, ny)
        return volume
    return 0

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

for _ in range(K):
    ax, ay, bx, by = map(int, input().split())
    for i in range(ax, bx):
        for j in range(ay, by):
            paper[j][i] = 1

count = 0
volume_list = []

for i in range(M):
    for j in range(N):
        volume = 0
        if dfs(i, j) >= 1:
            count += 1
            volume_list.append(volume)

volume_list.sort()

print(count)
print(" ".join(map(str, volume_list)))

---

코드 설명

1. 모눈 종이

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

for _ in range(K):
    ax, ay, bx, by = map(int, input().split())
    for i in range(ax, bx):
        for j in range(ay, by):
            paper[j][i] = 1

위에서 설명한 모눈종이를 2차원 리스트로 만드는 과정이다.

M * N 크기의 2차원 리스트를 초기화 해주고, 직사각형은 1로 표현해준다. 

그림과 리스트가 대칭이여도 값을 구하는데 문제가 없다.

 

위쪽은 문제에 있는 그림, 아래쪽은 코드를 실행했을때 나오는 리스트다.

2. dfs

for i in range(M):
    for j in range(N):
        volume = 0
        if dfs(i, j) >= 1:
            count += 1
            volume_list.append(volume)

이제 각 한칸마다 dfs를 해본다. dfs의 리턴값은 빈공간의 넓이를 리턴한다.

따라서 1이상이면 빈공간이 존재한다는 뜻이므로 count값을 증가시켜준다.

dfs함수는 다음과 같다.

def dfs(x, y):
    global volume
    if x < 0 or x >= M or y < 0 or y >= N:
        return 0

    if paper[x][y] == 0:
        volume += 1
        paper[x][y] = 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            dfs(nx, ny)
        return volume
    return 0

방문한 칸의 값이 0이라면 상하좌우에 있는 좌표를 방문한다.

모든 탐색이 끝나면 넓이(volume)를 리턴해준다.