[Python] 🥈 백준 2583 영역구하기 / DFS & BFS 그림 풀이

 

2583번: 영역 구하기

 

 

문제 풀기 전 생각하기

 

문제 풀기 전 어려웠던 점이 보통 [0,0] 은 왼쪽 위에부터 시작해서 아래로 내려가는 형식인데 

아래에서부터 위로 숫자가 커지는 형식이라 그래프를 어떻게 생각해야될지 헷갈렸다.... 

그래서 그냥 표를 돌려서 생각했다

그림을 오른쪽으로 돌리면 우리가 평소에 많이 봤던 좌표가 보인다! 

그렇다면 다음 문제는 꼭짓점으로만 주어지는 영역을 어떻게 채우냐인데.....

그림을 그려서 꼭짓점과 실제 표의 좌표를 비교해보니 

왼쪽 위 꼭짓점~ 오른쪽아래 꼭짓점을 적고, 그 자리의 좌표를 적어보니

오른쪽아래 꼭짓점에다 각각 -1씩 해주면 위치가 나온다! 

하지만 어차피 FOR문으로 돌릴거라 -1을 안 해주고 그냥 X2,Y2까지 선언해주면 된다

그리고 나서 많이 풀었었던 연결영역 요소 문제들처럼 풀어주면 된다~

 

DFS 풀이

 

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

m, n, k = map(int, input().split())
arr = [[0] * m for _ in range(n)]
#좌표 생성
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(x1, x2):     # 왼쪽 위 꼭짓점부터
        for j in range(y1, y2): # 오른쪽 아래 꼭짓점까지
            arr[i][j] = 1

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

def dfs(x, y):
    arr[x][y] = 1  # 방문 표시
    cnt = 1
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 0:
            cnt += dfs(nx, ny) #return되는 dfs값을 더해준다 
    return cnt

answer = []

for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            answer.append(dfs(i, j))

answer.sort()
print(len(answer))
for i in answer:
    print(i, end=" ")

 

BFS

#BFS
import sys
input = sys.stdin.readline
from collections import deque
m, n, k = map(int, input().split())
arr = [[0] * m for _ in range(n)]


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

answer = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()
cnt = 0

def bfs(x, y):
    global cnt
    q.append([x, y])
    arr[x][y] = 1  # 방문 표시

    while q:
        x1, y1 = q.popleft()
        for i in range(4):
            nx = x1 + dx[i]
            ny = y1 + dy[i]

            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 0:
                q.append([nx, ny])
                arr[nx][ny] = 1  # 방문 표시
                cnt += 1

for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            cnt = 1
            bfs(i, j)
            answer.append(cnt)

answer.sort()
print(len(answer))

for i in answer:
    print(i, end=" ")

 

예전에 풀었던 단지번호 매기기와 비슷한 문제라 쉽게 풀 수 있었다