[알고리즘/BFS & DFS] 2583번 : 영역 구하기 - python

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

2583번: 영역 구하기

 

 

---

• 문제
• 소요시간: 47분5초

---

• 설계하기(접근방법) 

1. 입력받기

행열을 입력받는다

 

2. 구현하기

graph를 이전 문제들은 입력받았었다면

이번에는 직사각형의 위치를 입력받아

직사각형의 위치를 제외해주고

bfs로 넓이를 탐지해주면 된다

그 후 직사각형의 넓이를 리스트에 append해준다

 

3. 출력하기

직사각형 배열의 길이와

넓이들을 정렬해서 출력해준다

 

 

---

• 코드(출력)

from collections import deque

m, n, rectangle = map(int, input().split())
visited = [[0] * n for _ in range(m)]
graph = [[1] * n for _ in range(m)]
draw = []
draw_cnt = 0

def bfs(x, y):
    count = 1
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque()
    q.append([x,y])
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < m and 0<= ny < n:
                if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                    visited[nx][ny] = 1
                    count += 1
                    q.append([nx,ny])
    return count



## 좌표 x,y 다른거 유의
# 입력받은 위치 시작 이상 입력받은 위치 마지맞 미만
for _ in range(rectangle):
    start_y, start_x, end_y, end_x = map(int, input().split())
    for i in range(start_x, end_x):
        for j in range(start_y, end_y):
            graph[i][j] = 0

for i in range(m):
    for j in range(n):
        if visited[i][j] == 0 and graph[i][j] == 1:
            visited[i][j] = 1
            c = bfs(i,j)
            draw_cnt += 1
            draw.append(c)

draw.sort()

print(draw_cnt)
print(*draw)

---

• 얻어갈 부분

1. 구현은 20분만에 끝냈는데, 또 ny = x + dy[i]로 선언해서 20분동안 디버깅을 했다. 꼭 주의하고 디버깅할 때 1순위로 찾아보자