[Python][백준] 2583. 영역 구하기/ 그래프 탐색,DFS,BFS (S1)

링크🔗

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

---

🗒️파이썬 코드 풀이 (DFS)

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

for _ in range(K):
    j1, i1, j2, i2 = map(int, input().split())
    for i in range(i1, i2):
        for j in range(j1, j2):
            lst[i][j] = 1
            
di, dj = [0, -1, 0, 1], [1, 0, -1, 0]
rs = []


def dfs(i, j):
    global count
    lst[i][j] = 1
    count += 1
    for k in range(4):
        ni, nj = i + di[k], j + dj[k]
        if 0 <= ni < N and 0 <= nj < M and lst[ni][nj] == 0:
            dfs(ni, nj)


for i in range(N):
    for j in range(M):
        if lst[i][j] == 0:
            count = 0
            dfs(i, j)
            rs.append(count)

print(len(rs))
print(" ".join(list(map(str, sorted(rs)))))

 

1. DFS로 푸는 방법에 대해 먼저 알아보자. 

직전 포스트(연결 요소의 개수 문제) 와 느낌이 비슷한 문제 

🚨 해당 문제는를 봤을때, DFS나 BFS로 di,dj를 생각하여 ni,nj를 만들어 줄 생각을 한다.

 

2. 문제에서 M,N 크기의 배열이 나타나는데,

여기서 주의 해야 할 것은 작은 사각형을 하나의 좌표로 보는 것이다.  

(사각형의 꼭지점을 기준으로 보면 힘들어진다.)

ex)
(0,0) ㅡ (0,1) ㅡ (0,2)
  ㅣ (0,0) ㅣ (0,1)ㅣ
(1,0) ㅡ (1,1) ㅡ (1,2)
(이런식으로  작은 사각형을 하나의 좌표로 보면된다.)

이렇게 M * N 크기의 배열을 만들고
입력에 맞게 인덱싱 해주면된다.

 

3. 주어진 입력의 좌표를 바탕으로  인덱싱 할 때,

어떤 조건으로 할지 꼼꼼히 체크하고 코드를 작성한다.

(어떤식으로 할지 안정하면, 나중에 더 복잡해진다.)

 

현재 문제에서는 j1,i1,j2,i2의 역할 범위를 다 확인하고 변수 할당함

 

4. 직사각형이 그려진 좌표는 1, 그렇지 않은 것은 0으로 간주한다.

 

5. 이후 배열을 모두 돌면서, DFS를 한다. 

 

6. DFS를 할 때, 가장 먼저 매개변수로 주어진 i,j 위치를 0으로 바꿔주고,

해당 부분은 카운트 처리 해준다.

그리고 4 방향으로 ni,nj를 만들어 조건문에 맞게 돌려준다.

 

7. 조건문은 ni,nj가 범위 내이고, lst[ni][nj]가 0이여야 한다. 

 

🗒️파이썬 코드 풀이 (BFS)

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

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

for _ in range(K):
    j1, i1, j2, i2 = map(int, input().split())
    for i in range(i1, i2):
        for j in range(j1, j2):
            lst[i][j] = 1

di, dj = [0, -1, 0, 1], [1, 0, -1, 0]
rs = []

def bfs(i, j):
    global count
    count = 1
    q = deque([[i, j]])
    lst[i][j] = 1
    while q:
        v = q.popleft()
        for k in range(4):
            ni, nj = v[0] + di[k], v[1] + dj[k]
            if 0 <= ni < N and 0 <= nj < M and lst[ni][nj] == 0:
                q.append([ni, nj])
                lst[ni][nj] = 1
                count += 1

for i in range(N):
    for j in range(M):
        if lst[i][j] == 0:
            count = 0
            bfs(i, j)
            rs.append(count)

print(len(rs))
print(" ".join(list(map(str, sorted(rs)))))

 

1. 이번에는  BFS 방식으로 푸는 법에 대해 알아보자.

BFS도 크게 다른 것은 없다. (전반적으로 DFS랑 비슷하다.)

 

2. BFS도 똑같이 배열에 대한 for 문을 돌려준다. 

 

3. bfs 함수를 실행 할 때,  먼저 카운트를 해주고 Queue 자료구조를 만들어준다.

(가장 첫번째로 들어가는 것은 [0][0]이 될 것이다. )

 

4. 그리고 while문으로 q가 비워질 때 까지 반복한다.

4가지 방향에 대해 조건문을 걸어주고,

아직 카운트 하지 않은 사각형의 좌표를 q에 넣어주고 카운트 한다. 

 

 

📌  문제 코멘트

맨 처음에 사각형 자체를 좌표로 보지 않고,  

사각형의 꼭지점을 좌표로 봐서 시간이 오래  걸렸었다.

 

그 외의 DFS,BFS 구현 자체는 그다지 어렵지 않았다. 

DFS/ BFS + 방향 찾기 만 잘 이해하면 비교적 쉽게 풀린다. 

(DFS/BFS의 특유의 느낌 ...? 이 있는데, 많이 풀다보면 감이 잡히는거 같다.)

 

(이것들을 텍스트로 설명하려니 어렵다 ...)

---

📚문제

눈금의 간격이 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