[bfs/백준] 2583번 : 영역 구하기

- 문제 : https://www.acmicpc.net/problem/2583

 

문제 이해 

- 좌표로 주어지는 영역을 제외한 부분 중에 독립된 영역의 개수와 각 영역의 크기를 출력하는 문제다.

- 일단 사각형 넓이만큼 행렬을 채운 뒤 나머지 빈 영역을 bfs로 탐색하면 된다고 이해했다. 

- 전반적으로 쉬운 문제였지만 좀 어려웠던 부분이 주어진 좌표를 행렬 인덱스로 변경하는 것이었다. 

 

풀이 로직 

- 기본 값을 받은뒤 주어진 (x1, y1), (x2, y2) 좌표를 가지고 matrix에 영역을 1로 채운다.

- 행렬을 채우는 코드는 다음과 같은데 하나의 사각형은 행 (m - y2) ~ (m - y1), 열 x1 ~ x2 의 영역을 차지한다. 

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split()) # 좌표 (x1, y1)은 (m - y1)행 x1열
    for i in range(m - y2, m - y1):
        for j in range(x1, x2):
            matrix[i][j] = 1

- 주어진 x1, y1, x2, y2를 바로 사용하지 않은 이유는 좌표와 행렬 인덱스의 구조가 다르기 때문이다.

아래 그림으로 이해해보면 행렬은 (0,0)이 왼쪽 위인 반면에 좌표는 (0,0)이 왼쪽 아래다. 그래서 좌표에서 x좌표는 열을 의미하고, y좌표는 행을 의미한다. 또한 열은 행렬과 좌표 모두 동일하지만 행의 경우 거꾸로 되어있어서 (행렬 가로길이 - y좌표)값이 좌표를 행렬로 바꾼 것이다. 

- matrix에 각 사각형을 채웠으면 방문하지 않고, matrix 값이 0인 지점들을 기준으로 bfs를 실행한다. 

- 영역의 전체 개수와 각 영역의 넓이를 출력한다. (전체 개수도 출력해줘야 한다. 문제를 잘 읽자!)

정답 풀이 

m, n, k = map(int, input().split())
matrix = [[0] * n for _ in range(m)]
visit = [[0] * n for _ in range(m)]

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split()) # 좌표 (x1, y1)은 (m - y1)행 x1열

    for i in range(m - y2, m - y1):
        for j in range(x1, x2):
            matrix[i][j] = 1

def bfs(x, y, visit, matrix):   
    queue = [[x, y]]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    count = 1
    while queue: 
        x, y = queue.pop(0)
        visit[x][y] = 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if not visit[nx][ny] and matrix[nx][ny] == 0:
                    count += 1
                    visit[nx][ny] = 1
                    queue.append([nx, ny])
    return count    

answer = []
for i in range(m):
    for j in range(n):
        if not visit[i][j] and matrix[i][j] == 0:
            answer.append(bfs(i, j, visit, matrix))
            
answer.sort()
print(len(answer))
for i in range(len(answer)):
    print(answer[i], end = ' ')