[BFS&DFS] 백준_2583_영역구하기

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

2583번: 영역 구하기

문제 

입력 

풀이 

처음에는 좌표로 왼쪽 아래에서 시작해야할 것 같아서 이 그림을 어떻게 뒤집을까 고민했는데 

생각해보니 왼쪽 위에서부터 시작하면 그냥 아래에 거울 둔것처럼 뒤집히기 때문에 영역(너비)구하는데에는 무리가 없어서 2차원 배열로 풀어줬음! 

사용 알고리즘 : BFS

이 문제를 처음 보자마자 든 생각은 좌표에 해당하는 직사각형 너비는 다 1로 만들어주고 직사각형 너비에 해당하지 않는 부분은 0으로 만들어주면 BFS의 대표적인 미로찾기 문제처럼 0과 1로 이루어진 좌표를 만들 수 있었음.  여기서는 겹치는 부분도 존재했기 때문에 직사각형 너비에 대한 부분은 +1씩 해줬음. 

나는 BFS 알고리즘을 풀 때 기본적인 BFS함수의 틀을 만들어놓고 시작한다. 

def bfs(x, y):
    cnt = 0 
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    queue = deque()
    queue.append((x, y))

    while(queue):
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= len(ground) or ny >= len(ground[0]):
                continue
            if ground[nx][ny] >= 1:
                continue
            if ground[nx][ny] == 0:
                ground[nx][ny] = 1
                queue.append((nx, ny))
                cnt += 1
    if cnt == 0 :
        cnt = 1
    return cnt

• 여기서는 다른 BFS문제들과 달리 좌표의 값이 0일 경우에만 방문처리를 해주고 cnt를 활용해서 너비를 구해줬음 
• 마지막에 if문에서 자꾸 너비가 1인 애의 너비가 0으로 나와서 넣어준 것인데 .. 다른 처리가 필요하다고 생각하는데 아무나 지적해주세요 

전체코드 

from collections import deque

N, M, K = map(int, input().split())
rectangle_list = list()
ground = [[0 for col in range(M)] for row in range(N)]

def bfs(x, y):
    cnt = 0 
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    queue = deque()
    queue.append((x, y))

    while(queue):
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= len(ground) or ny >= len(ground[0]):
                continue
            if ground[nx][ny] >= 1:
                continue
            if ground[nx][ny] == 0:
                ground[nx][ny] = 1
                queue.append((nx, ny))
                cnt += 1
    if cnt == 0 :
        cnt = 1
    return cnt

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    rectangle_list.append([[x1, y1], [x2, y2]])

for i in range(K):
    for j in range(rectangle_list[i][0][1], rectangle_list[i][1][1]):
        for k in range(rectangle_list[i][0][0], rectangle_list[i][1][0]):
            ground[j][k] += 1

result = list()

for i in range(N):
    for j in range(M):
        if ground[i][j] == 0:
           result.append(bfs(i, j))
result = sorted(result)
print(len(result))
for i in range(len(result)):
    print(result[i], end=' ')

• rectangle_list: [[직사각형 시작점], [직사각형 끝점]]
• ground: 직사각형을 표시하기 위한 2차원 리스트, 너비도 구해주기 위한 리스트
  • ground의 값이 0일 경우에만 방문해서 bfs로 너비 구해줌