[백 준/DFS/BFS] 2583: 영역 구하기

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

2583번: 영역 구하기

핵심 아이디어

먼저 0으로 초기화된 배열을 생성해준다. 그리고 직사각형이 포함된 영역에 대해 1을 더해준다.

• DSF 탐색 알고리즘 활용. (BFS로도 가능)
• setrecursionlimit(10**6) 재귀의 깊이를 늘려줘야함

import sys
sys.setrecursionlimit(10**6)

m, n, k = map(int, input().split())
# 처음에 그래프를 0으로 초기화
graph = [[0] * n for _ in range(m)]
for _ in range(k):
	x1,y1,x2,y2 = map(int, input().split())
	# 사각형이 있는 부분을 1로 만든다.
	for i in range(y1,y2):
		for j in range(x1,x2):
			graph[i][j] = 1


def dfs(x,y):
	global count
	if x < 0 or x >=m or y < 0 or y >=n:
		return False
	if graph[x][y] == 0: # 분리된 영역이라면
		count += 1 # 넓이를 구하기 위해 1 증가
		graph[x][y] = 1 # 방문했다는 의미로 1로 바꿔줌
		dfs(x-1,y)
		dfs(x+1,y)
		dfs(x,y-1)
		dfs(x,y+1)
		return True
	return False

result = 0 # 분리된 영역 개수 셀 변수
count = 0 # 각 영역의 넓이를 셀 변수
ans = [] # 넓이를 넣어줄 list

for i in range(m):
	for j in range(n):
		if dfs(i,j): # 분리된 영역을 구했다면
			result += 1
			ans.append(count)
			count = 0 # 영역의 넓이 초기화
ans.sort()
print(result)
for i in ans:
	print(i, end=' ')

그래프 모양에 대해서 다시 살펴보면 다음과 같다. 이 그래프를 뒤짚으면 문제에서 요구하는 표가 된다.

temp = [[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):
			temp[i][j] = 1
for i in temp:
    print(i)
[0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 1, 1, 0]
[1, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0]

temp = [[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):
			temp[i][j] = 1
temp_reversed = temp[::-1]
for i in temp_reversed:
	print(i)
[0, 1, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0]
[0, 1, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 1, 1, 0]

참고 블로그

처음에 구글링을 하다 내가 짠 로직과 비슷하지만 뭔가 달라서 헤매던 와중에 나와 로직이 똑같은 블로그를 발견하고 참고하였다.

https://codingwonny.tistory.com/171

백준 2583 번. 영역 구하기 (Python / 파이썬)