[Baekjoon] #2583 영역 구하기 (Python)

📝 문제

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

💬 풀이 방법

아이디어

기본적인 DFS, BFS 알고리즘을 활용하는 문제이다. 격자 내부에 이동할 수 없는 벽이 있다는 점을 제외하면, 탐색의 경로 자체에 큰 특징이 있는 것은 아니기 때문에 BFS가 적합하다. 해당 문제의 경우에는 DFS를 사용해도 무방하지만, 재귀를 사용하기 때문에 sys.setrecursionlimit() 함수를 활용하여 재귀 한도를 해제해야 한다.

알고리즘

• BFS

1. 격자의 정보와 직사각형의 정보를 입력 받은 뒤, 직사각형이 위치한 곳의 값을 1로 설정한 graph 배열을 완성한다.
2. 해당 격자를 반복문을 활용하여 탐색하면서 값이 0인 곳의 좌표를 deque 객체에 삽입한다.
3. deque 객체의 왼쪽에서부터 값을 꺼내온다.
4. 해당 좌표 주변에 값이 0인 곳이 있다면 해당 위치로 이동하고, cnt 변수에 1을 더한다. (이 때, cnt의 초기 값은 1이다.)
5. 반복이 끝났다면 cnt의 값을 res 배열에 삽입하고, 전체 탐색이 끝난 뒤 res의 길이와 정렬된 res의 원소를 차례로 출력한다.

• DFS

1. BFS와 동일하게 격자의 정보를 입력받는다.
2. 격자를 탐색하고, 값이 0인 곳의 좌표를 찾는다면 해당 위치에서부터 dfs() 함수를 실행한다.
3. 해당 위치의 값을 1로 변경하고 cnt에 1을 더한 뒤, 주변에 값이 0인 곳을 찾는다.
4. 값이 0인 곳이 있다면 해당 위치로 이동하여 2번 과정부터 다시 반복한다.
5. 더 이상 이동할 수 있는 곳이 없다면 cnt를 반환하고 res 배열에 삽입한다.
6. 탐색을 모두 끝마친 뒤 res 배열의 길이와 정렬된 원소를 차례로 출력한다.
   
   

💻 소스코드

• BFS

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

m, n, k = map(int, input().split())

graph = [([0] * n) for _ in range(m)]
q = deque()

for _ in range(k):
	a, b, c, d = map(int, input().split())
	for i in range(b, d):
		for j in range(a, c):
			graph[i][j] = 1

def can_go(x, y):
	return 0 <= x < n and 0 <= y < m

def bfs(i, j):
	cnt = 1
	q.append((i, j))

	dxs, dys = [0, 0, -1, 1], [1, -1, 0, 0]

	while q:
		y, x = q.popleft()

		for dx, dy in zip(dxs, dys):
			ny, nx = y + dy, x + dx

			if can_go(nx, ny) and not graph[ny][nx]:
				cnt += 1
				graph[ny][nx] = 1
				q.append((ny, nx))

	return cnt


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(100000)
input = sys.stdin.readline

m, n, k = map(int, input().split())

graph = [([0] * n) for _ in range(m)]

for _ in range(k):
	a, b, c, d = map(int, input().split())
	for i in range(b, d):
		for j in range(a, c):
			graph[i][j] = 1

def can_go(x, y):
	return 0 <= x < n and 0 <= y < m

def dfs(y, x):
	global cnt

	graph[y][x] = 1
	cnt += 1
	dxs, dys = [1, -1, 0, 0], [0, 0, 1, -1]

	for dx, dy in zip(dxs, dys):
		ny, nx = y + dy, x + dx
		if can_go(nx, ny) and not graph[ny][nx]:
			dfs(ny, nx)
		
	return cnt

res = []

for i in range(m):
	for j in range(n):
		if graph[i][j] == 0:
			cnt = 0
			res.append(dfs(i, j))

print(len(res))
print(*sorted(res))