[백준-2583] 영역 구하기 #DFS #BFS

1. 백준-2583 영역 구하기

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

 

2. 알고리즘 카테고리 : DFS, BFS

---

3. 나의 풀이 알고리즘(1차) : DFS

- 알고리즘을 보면서 리트코드의 섬찾기와 동일한 문제라고 생각이 들었다. 따라서 0인 공간을 따라서 상하좌우를 탐색하는 재귀 형식으로 문제를 풀이하였으나 "런타임 에러 (RecursionError)"를 보게 되었다. https://leetcode.com/problems/number-of-islands/

- Recursion Error는 Recursion이 시스템 설정 이상으로 깊게 들어가서 발생하는 오류로 임시적인 해결 방법으로는 sys.set recursion limit을 이용하여 한계치를 임의로 올려주는 방법이 있다. 하지만 이는 코테에서 요구한 조건이 아니고, 이러한 문제가 발생했을 경우 일반적으로 Stack을 사용한 방식으로 그래프 탐색을 할 수 있기 때문에 BFS를 사용해서 풀이를 다시 해주었다.

# DFS 시간초과 실패
from pprint import pprint
from copy import *
import copy
M, N, K = map(int, input().split())
matrix = [[0 for n in range(N)] for n in range(M)]
for k in range(K):
    y1, x1, y2, x2 = map(int, input().split())

    for x in range(x1, x2):
        for y in range(y1, y2):
            matrix[x][y] = 1

# M, N, K = 5,7,3
# matrix = [[0 for n in range(N)] for n in range(M)]
# for k in [[0,2,4,4],[1,1,2,5],[4,0,6,2]]:
#     y1, x1, y2, x2 = k[0], k[1], k[2], k[3]

    for x in range(x1, x2):
        for y in range(y1, y2):
            matrix[x][y] = 1
            # print(f'x={x},y={y}')
            # pprint(matrix)

pprint(matrix)

result = []
visited = []
def check(matrix, x, y):
    global count
    if x < 0 or x == M or y < 0 or y == N or matrix[x][y] != 0:
        return
    
    matrix[x][y] = 1
    count += 1

    pprint(matrix)
    print(f'x={x}, y={y},count={count}')
    check(matrix, x - 1, y)
    check(matrix, x + 1, y)
    check(matrix, x, y - 1)
    check(matrix, x, y + 1)

for i in range(len(matrix)):
    for j in range(len(matrix[0])):
        count = 0
        if matrix[i][j] == 0:
            check(matrix, i, j)
            result.append(count)
            count = 0

result = sorted(result)
print(len(result))
for r in result:
    print(r, end=" ")//코드작성

 

나의 풀이 알고리즘(1차) : BFS

- 풀이를 하면서 기존에 상하좌우 탐색을 각각 x,y에서 바꿔주는 것을 for문을 통한 처리로 변경해주었다. 

from pprint import pprint
from copy import *
from collections import deque

M, N, K = map(int, input().split())
matrix = [[0 for n in range(N)] for n in range(M)]
for k in range(K):
    y1, x1, y2, x2 = map(int, input().split())

    for x in range(x1, x2):
        for y in range(y1, y2):
            matrix[x][y] = 1

rx = [-1, 1, 0, 0]
ry = [0, 0, -1, 1]

def queue_bfs(x, y):
    visited = deque()
    visited.append((x,y))
    matrix[x][y] = 1
    count = 1
    while visited:
        nx, ny = visited.popleft()

        for index in range(4):
            mx = nx + rx[index]
            my = ny + ry[index]
            if 0 <= mx < M and 0 <= my < N and matrix[mx][my] == 0:
                matrix[mx][my] = 1
                count += 1
                visited.append((mx, my))
    return count

result = []
for x in range(M):
    for y in range(N):
        if matrix[x][y] == 0:
            result.append(queue_bfs(x,y))


result = sorted(result)
print(len(result))
for r in result:
    print(r, end= " ")