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

 

📚 영역 구하기

 

문제

눈금의 간격이 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개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

 

 

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

 

예제 입력 1 복사

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

예제 출력 1 복사

3
1 7 13

 

 

✍ 접근

• 문제를 이해하고 방법을 찾는다(여기서 막힘)
• BFS로 탐색하며 결과를 구한다 
• 🚨 x와 y list를 혼동하지 않게 주의

 

 

정답코드

# ✨ 구분 1
import sys
from collections import deque
input = sys.stdin.readline
M,N,K = map(int,input().split())

dx = [-1,0,1,0]
dy = [0,-1,0,1]

# ✨ 구분 2
board = [[0]*N for _ in range(M)]

for _ in range(K):
    x1,y1,x2,y2= map(int,input().split())
    for i in range(y1,y2):
        for j in range(x1,x2):
            board[i][j] = 1

# ✨ 구분 3      
res = []
def BFS(x,y):
    cnt = 1
    dq = deque([])
    dq.append((x,y))
    board[x][y] = cnt
    while dq:
        p = dq.popleft()
        for i in range(4):
            new_x = p[0] + dx[i]
            new_y = p[1] + dy[i]
            if 0<= new_x <M and 0<= new_y < N and board[new_x][new_y] == 0 :
                board[new_x][new_y] = 1
                cnt+=1
                dq.append((new_x,new_y))
    res.append(cnt)

# ✨ 구분 4
for i in range(M):
    for j in range(N):
        if board[i][j] == 0 :
            BFS(i,j)

# ✨ 출력
print(len(res))
res.sort()
print(*res)

구분 1

• 기본적인 입력을 받고
• BFS로 2중 리스트 board를 순회할 예정이서서 관련 코드도 미리 짜놓는다

구분 2 📌

• 이 부분에서 많이 고생했다. 기본적인 사각형에서 사용되는 좌표와 2차원 배열의 위치를 비교해보고 별 짓을 다 해봤지만 어려웠다.
  답은 그냥 사각형의 특징을 이용하는 것이다. 
• board를 설정해주고

for _ in range(K):
    x1,y1,x2,y2= map(int,input().split())
    for i in range(y1,y2):
        for j in range(x1,x2):
            board[i][j] = 1

• for문을 통해 돌아주는데, 잘 보면 range의 크기가 x1,y1이 아니라 y1,y2 // x1,x2이e다.
  
  1. 가로와 세로를 잘 생각해야 한다. x가 가로축, y가 세로축인 기존 사각형에 비해 우리가 만들고자 하는 이중 리스트 사각형의 가로와 세로는 뒤바뀌어 있다
     => y range를 먼저 도는 이유
  2. 문제를 보면 x1.y1는 좌측 하단 좌표, x2,y2는 우측 상단 좌표이다
     => 더 큰 x값에서 작은 x 값을 뺀 값이 만약 3이라고 했을 때, 이 사이를 한 줄씩 돌면서 칠해줄 수 있다
     => y도 마찬가지
     => 이해가 안된다면 키보드의 텐키를 칠하는 방법을 생각해보면 된다.
     우측 상단 좌표(9)가 3,3
     좌측 하단 좌표(1)이 1,1
     이라고 생각했을 때
     3-1을 빼서 가운데를 도는 것을 3번 반복하면 == 2중 for문을 사용하면 텐키를 다 칠할 수 있다
     
     설명이 더 복잡한 느낌인데.. 아무튼 사각형을 한번 그려보면 이해가 될 것.
     
     사실 이 방법을 생각하지 못해서 고전한 사람은 나밖에 없을 것 같기는 하다 😣   
• 아무튼 이렇게 for문을 돌면서 board[i][j]를 1로 채워준다.

 

구분 3,4

• 단지번호붙이기 문제와 매우 유사한 방식으로 풀면 된다.
• 이중 for문을 통해 board가 0인 부분을 찾으면
  • BFS 함수로 들어가서 board가 0인 부분의 수를 카운트해준다
  • while문이 끝나면 cnt에 세어진 수를 res로 보내면 된다

 

출력

• 출력!

 

⭐ 배움

• 가로 세로를 잘 구분하자