[파이썬/Python] 백준 2583번 영역 구하기

[파이썬/Python] 백준 2583번 영역 구하기

2583번: 영역 구하기

---

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

 

해설

간단한 DFS 문제이다. 다만 각 영역마다 넓이를 구해줘야 하므로, 재귀호출이 끝날때마다 그 값을 저장 또는 반환해주어야한다.

1. 전체 직사각형 범위의 값을 0으로, K개의 직사각형이 차지하는 범위의 값을 1로 할당한다.

2. dfs를 통해 상하좌우를 방문하면서 0일 경우, 방문표시를 위해 1로 값을 할당한다.

3. 재귀횟수를 함께 파라미터로 넘겨 주고, 재귀가 끝났을 경우 그 횟수를 반환해준다.

4. K번 동안 2~3 과정을 반복하면서 반환된 값을 리스트에 저장한다.

5. 리스트의 길이가 곧 직사각형의 수이며, 직사각형의 크기가 리스트에 저장된다. 

 

코드

import sys
sys.setrecursionlimit(10000)

M, N, K = map(int, sys.stdin.readline().split())

field = [[0 for _ in range(N)] for _ in range(M)] 

for _ in range(K):
    X1, Y1, X2, Y2 = map(int, sys.stdin.readline().split())
    for Y in range(Y1, Y2):
        for X in range(X1, X2):
            field[Y][X] = 1

def dfs(x, y, count):
    field[y][x] = 1
    for dx, dy in d:
        X, Y = x + dx, y + dy
        if (0 <= X < N) and (0 <= Y < M) and field[Y][X] == 0:
            count = dfs(X, Y, count+1)
    
    return count

area = []
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

for Y in range(M):
    for X in range(N):
        if field[Y][X] == 0:
            area.append(dfs(X, Y, count=1))

print(len(area))
print(*sorted(area))

 

풀이

import sys
sys.setrecursionlimit(10000)

M, N, K = map(int, sys.stdin.readline().split())

field = [[0 for _ in range(N)] for _ in range(M)]

1. 재귀 횟수를 설정해준다. M, N, K 를 입력 받고 0으로 할당된 M*N 크기의 직사각형 리스트를 만들어준다.

 

for _ in range(K):
    X1, Y1, X2, Y2 = map(int, sys.stdin.readline().split())
    for Y in range(Y1, Y2):
        for X in range(X1, X2):
            field[Y][X] = 1

2. 차지하는 직사각형 범위를 1로 할당해준다.

 

area = []
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

for Y in range(M):
    for X in range(N):
        if field[Y][X] == 0:
            area.append(dfs(X, Y, count=1))

3. N*M 직사각형을 전부 돌면서, 분리된 영역(리스트에서 0이 할당된 값)을 찾고, DFS 함수를 호출해준다.

0이 할당된 시작점부터 크기에 반영되므로, count 파라미터로 1을 넘겨준다.

 

def dfs(x, y, count):
    field[y][x] = 1
    for dx, dy in d:
        X, Y = x + dx, y + dy
        if (0 <= X < N) and (0 <= Y < M) and field[Y][X] == 0:
            count = dfs(X, Y, count+1)
    
    return count

4. 이미 방문한 영역을 표시하기 위해 1로 할당해준다.

상하좌우를 돌면서, 리스트의 영역을 넘지 않았고 0이 값으로 할당된 경우

dfs 함수를 다시 한번 호출해주고 그 값을 count 에 저장한다.

count 를 반환해줌으로서 호출된 횟수(분리된 영역의 크기)를 구해줄 수 있다.

 

print(len(area))
print(*sorted(area))

5. 분리된 직사각형의 수와 분리된 직사각형의 크기를 출력해준다.

 

피드백

1. 재귀횟수를 어떻게 측정하는가에 대한 아이디어를 떠올리는게 힘들었다.

count 를 dfs 에 파라미터로 넘겨주는 것까지는 생각할 수 있었으나,

그 함수 안에서 측정된 값을 온전히 반환해주는 것은 생각하기 힘들었다.

앞으로도 재귀호출 시에 그 함수 안에서의 값이 필요하다면 반환된 값을 다시 파라미터에 저장하는 방법을 활용할 것이다.

 

2. 파이썬 리스트 요소 출력 Asterisk(*)에 대한 내용도 처음 알았다.

찾다보니 deep copy, shallow copy, 파이썬 리스트 자료구조, 포인터 개념 등 여러가지 또한 복습하게 되었다.

Python 리스트 요소 한줄에 한번에 출력하기