[백준/Python] 2583번(그래프, BFS, DFS)_영역 구하기

📌문제 유형

그래프 이론, 그래프 탐색, BFS, DFS (실버1)

 

📌문제

2583번: 영역 구하기

 

📌나의 문제풀이

- BFS로 풀이

from collections import deque

m,n,k = map(int,input().split())    # n = x, m = y
maps = [[1] * 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):
            maps[i][j] = 0


result = []
q = deque()

for x in range(n):
    for y in range(m):
        if maps[x][y] == 1:
            ans = 0
            q.append((x,y))
            maps[x][y] = 0

            while q:
                x_,y_ = q.popleft()
                ans += 1

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

                for l in range(4):
                    nx = x_ + dx[l]
                    ny = y_ + dy[l]

                    if 0 <= nx < n and 0 <= ny < m:
                        if maps[nx][ny] == 1:
                            maps[nx][ny] = 0
                            q.append((nx,ny))
            result.append(ans)
print(len(result))
result.sort() 
print(*result)

 

📌 다른사람의 문제풀이

백준 알고리즘 2583번 영역 구하기(python)

- BFS 풀이

from collections import deque

def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    cnt = 1
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == 0:
                graph[Y][X] = 1
                queue.append((Y, X))
                cnt += 1
    return cnt
    
M, N, K = map(int, input().split())
graph = [[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):
            graph[i][j] = 1
res = []
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            graph[i][j] = 1
            res.append(bfs(i, j))
print(len(res))
print(*sorted(res))

 

- DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(y, x, cnt):
    graph[y][x] = 1
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == 0:
            cnt = dfs(Y, X, cnt+1)
    return cnt
    
M, N, K = map(int, input().split())
graph = [[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):
            graph[i][j] = 1
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = []
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            res.append(dfs(i, j, 1))
print(len(res))
print(*sorted(res))

 

📌 리뷰 

-  DFS 종료 조건 : cnt = dfs(x,y), 마지막에 return cnt로 간단히 해결하기