문제
접근
2차원 BFS 문제이다.
조금 색다른 점은 입력이 좌표 형식이란 점과 주어지는 영역들이 벽이 된다는 점이다.
좌표로 주어지는 값이 배열의 index와 조금 달라서, 편의를 위해 좌표 변환 작업을 따로 수행해주었다.
coordinateTransformation 함수는 주어지는 좌표를 편하게 board의 배열 좌표로 변환하며, 왼쪽위의 좌표와 오른쪽 아래좌표로 바꿔준다.
boardDraw 함수는 변형된 좌표를 가지고 board 판에 벽을 그려준다.
코드
- 파이썬 코드
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
44
45
46
from collections import deque
def coordinateTransformation(x1, y1, x2, y2):
y1 = h - y1
y2 = h - y2
return x1, y2, x2, y1
def boardDraw(x1, y1, x2, y2):
for i in range(y1, y2):
for j in range(x1, x2):
board[i][j] = 0
def bfs(sx, sy):
dx = [0,0,-1,1]
dy = [1,-1,0,0]
q = deque()
q.append((sx,sy))
board[sy][sx] = 2
size = 1
while q:
nowx, nowy = q.popleft()
for x, y in zip(dx, dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= w or ny < 0 or ny >= h:
continue
if board[ny][nx] == 1:
board[ny][nx] = 2
q.append((nx,ny))
size+=1
return size
h, w, k = map(int, input().split(' '))
board = [[1]*w for _ in range(h)]
for _ in range(k):
x1, y1, x2, y2 = map(int, input().split(' '))
x1, y1, x2, y2 = coordinateTransformation(x1, y1, x2, y2)
boardDraw(x1, y1, x2, y2)
ans = []
for i in range(h):
for j in range(w):
if board[i][j] == 1:
ans.append(bfs(j,i))
ans.sort()
print(len(ans))
for item in ans:
print(item, end=' ')