[Python] 백준 2583 영역 구하기

📌 문제

2583번: 영역 구하기

 

 

✔️ 요약

직사각형을 그린 후 남은 나머지 영역에 대해, 아래 두 개의 결과를 출력

① 분리된 영역의 개수

② 분리된 영역의 넓이를 오름차순으로 정렬 

 

📌 관련 개념 정리 (DFS)

. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식

. 일반적으로 재귀호출을 사용하여 구현

. 갈림길이 나타날 때마다 '다른 길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 '이 길은 아님'이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료.

 

📌 풀이

1. 파이썬은 재귀한도가 정해져 있으므로 sys.setrecursionlimit() 을 이용하여 한도를 늘린다.

import sys
sys.setrecursionlimit(1000000)

 

 

2. 세로, 가로, 직사각형 개수를 입력받고, 가로x세로 크기의 array를 만든다.

m, n, k = map(int,input().split()) # 모눈종이 세로, 가로, 직사각형 개수
array = [[0] * n for _ in range(m)] # 모눈종이

 

> 입력: 5 7 3

 

 

3. 반복문을 통해 주어진 사각형의 범위는 1로 칠한다.

for _ in range(k):
    # 왼쪽 아래 꼭짓점, 오른쪽 위 꼭짓점 좌표
    l_x, l_y, r_x, r_y = map(int,input().split()) 

    for i in range(l_y, r_y):     # 모눈종이의 세로를 y 좌표만큼 
        for j in range(l_x, r_x): # 모눈종이의 가로를 x 좌표만큼
            array[i][j] = 1       # 1로 만들어주기 (직사각형 표시)

※ 파이썬의 range(시작, 끝)은 "시작 ≤ 범위 ＜끝" 이다

 

3-1. 가장 큰 반복문은 직사각형의 수(= k) 만큼 반복한다.

   → 현재 진행하는 사각형의 꼭지점 값을 받는다.

 

3-1-1. 현재 진행하는 사각형의 y좌표 수 만큼 반복한다.

3-1-1-1. 현재 진행하는 사각형의 x좌표 수 만큼 반복한다.

   → 현재 위치를 1로 변경한다.

 

.

 

✔️ k=3이므로, 총 3개의 사각형을 그리기 위해 가장 큰 반복문은 3회 반복한다.

 

1>> 입력: 0 2 4 4

 

2>> 입력: 1 1 2 5

 

3>> 입력: 4 0 6 2

 

 

4. 분리된 영역을 구하고, 넓이를 구한다.

4-1. 모눈종이의 세로만큼 반복

4-1-1. 모눈종이의 가로만큼 반복

    4-1-1-1 현재 위치가 색칠되지 않은 경우 True가 반환되므로 result += 1을 하게 되며, 해당 영역 넓이를 받는다. (5-1)

    4-1-1-2 현재 위치가 이미 색칠되어 있는 경우는 False를 반환하므로 dfs 재귀를 타지 않고 다음 칸으로 이동한다. (5-2)

result = 0 # 분리된 영역 개수 셀 변수
count = 0  # 각 영역의 넓이를 셀 변수
ans = []   # 넓이를 넣어줄 list
for i in range(m):
    for j in range(n):
        if dfs(i, j):   # 분리된 영역을 구했다면
            result += 1 # 개수 count
            ans.append(count) # 구한 영역의 넓이 삽입
            count = 0         # 영역의 넓이 초기화

 

 

5. 현재 위치 기준으로 좌우상하를 탐색한다.

5-1. 시작점 값이 색칠되지 않은 경우(= 0), 좌우상하 순으로 타고 들어가면서 연결되어있는 지점들을 dfs 재귀를 통해 다 찾아내서 색칠한다. 연결된 공간들을 다 색칠하게 되면 dfs 재귀가 끝나고 마지막으로 True를 반환하며 4-1-1로 돌아간다.( 4-1-1-1)

5-2. 시작점 값이 색칠 된 경우(= 1), 바로  False를 반환하기 때문에 dfs재귀 없이 반환되며 4-1-1로 돌아간다.(4-1-1-2)

def dfs(x, y):
    global count  

    if x < 0 or x >= m or y < 0 or y >= n: 
        return False # 범위를 벗어나면 False 반환
    
    if array[x][y] == 0: # 분리된 영역이라면
        count += 1       # 넓이 구하기 위해 count 증가
        array[x][y] = 1  # 방문했다는 의미로 1로 바꿔줌
        # 좌, 우, 상, 하 탐색
        dfs(x - 1, y)    
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        return True   # 탐색 완료했다면 True 반환

    return False

6. 영역 넓이를 정렬하고 출력한다

ans.sort()  # 각 영역의 넓이 오름차순 정렬

print(result) 
for i in ans:
    print(i, end = ' ')

 

 

📌 전체 코드

import sys
sys.setrecursionlimit(1000000)

def dfs(x, y):
    global count  

    if x < 0 or x >= m or y < 0 or y >= n: 
        return False # 범위를 벗어나면 False 반환
    
    if array[x][y] == 0: # 분리된 영역이라면
        count += 1       # 넓이 구하기 위해 count 증가
        array[x][y] = 1  # 방문했다는 의미로 1로 바꿔줌
        # 상, 하, 좌, 우 탐색
        dfs(x - 1, y)    
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        return True   # 탐색 완료했다면 True 반환

    return False

m, n, k = map(int,input().split()) # 모눈종이 세로, 가로, 직사각형 개수

array = [[0] * n for _ in range(m)] # 모눈종이
for _ in range(k):
    # 왼쪽 아래 꼭짓점, 오른쪽 위 꼭짓점 좌표
    l_x, l_y, r_x, r_y = map(int,input().split()) 

    for i in range(l_y, r_y):     # 모눈종이의 세로를 y 좌표만큼 
        for j in range(l_x, r_x): # 모눈종이의 가로를 x 좌표만큼
            array[i][j] = 1       # 1로 만들어주기 (직사각형 표시)

result = 0 # 분리된 영역 개수 셀 변수
count = 0  # 각 영역의 넓이를 셀 변수
ans = []   # 넓이를 넣어줄 list
for i in range(m):
    for j in range(n):
        if dfs(i, j):   # 분리된 영역을 구했다면
            result += 1 # 개수 count
            ans.append(count) # 구한 영역의 넓이 삽입
            count = 0         # 영역의 넓이 초기화
ans.sort()  # 각 영역의 넓이 오름차순 정렬

print(result) 
for i in ans:
    print(i, end = ' ')