[백준] 2583 - 영역 구하기

2583번: 영역 구하기

✏️ 풀이

입력으로는 k개의 영역을 준다. 그래서 나는 x1, y1, x2, y2로 입력을 받았다. 이렇게 입력을 받아서 previsit으로 입력받은 영역을 방문 처리했다. 간단하게 표현하면 미로에서 벽을 세운 느낌으로 처리했다. 그리고 BFS를 통해서 영역의 너비를 계산했다. 

 

이문제에서는 처음 입력받은 좌표에 해당하는 구역만큼만 방문 처리를 했으면 금방 풀 수 있는 문제였다. BFS는 평소에 풀던 다른 문제처럼 처리를 하면 되는 거여서 금방 풀 수 있었다. 그리고 영역 처리하는게 좌표랑 배열 인덱싱하는거랑 반대로 해야해서 이거 해결하느라 시간 좀 오래 걸렸다.

💻 코드

import sys; input = sys.stdin.readline
from collections import deque

directions = [(1, 0),(0, 1),(-1, 0),(0, -1)]

def bfs(start):
    cnt = 1
    q = deque([start])
    visited[start[0]][start[1]] = True
    matrix[start[0]][start[1]] = cnt
    while q:
        v = q.popleft()
        for d in directions:
            x, y = v[0]+d[0], v[1]+d[1]
            if 0<=x<m and 0<=y<n and not visited[x][y] and matrix[x][y] != -1:
                cnt += 1
                q.append((x, y))
                visited[x][y] = True
                matrix[x][y] = cnt
    return cnt

def preVisit(start, dest):
    x, y = abs(start[0]-dest[0]), abs(start[1]-dest[1])
    for i in range(x):
        for j in range(y):
            matrix[start[1]+j][start[0]+i] = -1
            visited[start[1]+j][start[0]+i] = True

m, n, k = map(int, input().split())
matrix = [[0]*n for _ in range(m)]
visited = [[False]*n for _ in range(m)]
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    preVisit((x1, y1), (x2, y2))

result = [bfs((i, j)) for i in range(m) for j in range(n) if visited[i][j] == 0]
print(len(result))
print(*sorted(result))