공부 자료/알고리즘
(Python/파이썬) 백준 2583번 - 영역 구하기
뚜루뚜루세니
2021. 9. 7. 14:06
728x90
문제출처: https://www.acmicpc.net/problem/2583
2583번: 영역 구하기
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오
www.acmicpc.net
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
from collections import deque
#m = 세로, n=가로 , k= 직사각형 갯수
#bfs활용
m,n,k = map(int,input().split())
graph = [[0]*(n) for i in range(m)] #경로저장용 2차원 리스트
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
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
result = []
for i in range(m):
for j in range(n):
if graph[i][j] == 0:
count = 1
queue = deque([])
queue.append([i, j])
graph[i][j] = count
while queue:
y, x = queue.popleft()
for k in range(4):
nY = y + dy[k]
nX = x + dx[k]
if 0 <= nX < n and 0 <= nY < m and graph[nY][nX] == 0:
graph[nY][nX] = 1
queue.append([nY, nX])
count += 1
result.append(count)
print(len(result))
result.sort()
for num in result:
print(num,end=" ")
|
cs |
2. 해결과정
1번,2번 3번이 색칠되지 않은 분리된 영역이다. m,n,k 값과 좌표값이 주어질 때, 색칠되지 않은 부분이 몇개의 분리된 영역으로 나눠지는지, 분리된 영역의 넓이를 오름차순으로 나열하여 출력해주면 되는 문제이다.
BFS를 이용하여 구현하였고, 구역마다 탐색을 하기 위해서 반복문을 이용하여 그래프의 0이 존재하는 부분을 찾아 탐색해줬다.
3. 느낀점
어렵다... bfs dfs는 문제를 많이 풀어봐야 유형 파악이 쉽게 될 것 같다....
728x90