백준 2583 영역구하기

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

문제

• 인접한 노드(모눈종이 빈칸)들을 하나의 '뭉치'라고 했을 때, 몇개의 뭉치가 있는지 세고 각 뭉치의 넓이를 계산하는 문제.
• 백준 1012번 유기농배추와 유사한 문제(참고: https://yong-bro.tistory.com/30)
  • 단, 유기농 배추 문제와 비교했을 때 1)graph의 위 아래가 뒤집혀 있고 2)노드가 모서리 기준이므로 인덱스 계산시에 주의해야 함

오답노트

• x,y 좌표계와 행렬은 반대로 생각해야함. y가 행과 비슷한 성질이므로 행과 열은 좌표계에 올리면 y,x임.
• 좌표로 제시된 이 문제를 코드로 작성하니 결국 graph[y][x] = 1 와 같이 거꾸로 써줘야함. (아니면 애초에 행렬 좌표계로 바꿔서 생각하던가)

답안

• 주어진 사각형 정보를 활용하여 Graph 만들기
  • 인덱스가 직사각형 안에 들어오면 벽 세우기(graph[y][x] = 1)
• BFS 진행
  • 벽이 아닌것중에 방문안한곳 발견
    • cnt  +1
    • 인접한 노드 모두 방문처리. 방문처리 될 때 넓이 1 추가

import sys
import collections 

sys.stdin=open("input.txt","rt") 
m, n, k =  map(int,sys.stdin.readline().split())
graph = [[0]*n for _ in range(m)] # m행 n열
visited = [[0]*n for _ in range(m)]

for _ in range(k):
    x1,y1,x2,y2 = map(int,sys.stdin.readline().split()) #사각형 정보 입력
    for x in range(n):
        for y in range(m):
            if x>= x1 and x<= x2-1 and y >= y1 and y <= y2-1 :
                graph[y][x] =1  # 행/열을 좌표계로 올리면 y,x 꼴이 된다.
cnt =0    
dx =[1,0,-1,0]
dy =[0,1,0,-1]
q = collections.deque()
a = []
for i in range(m): #여기부턴 행/열 좌표계 이므로 위쪽 코드와 m n 순서가 다르다.
    for j in range(n):
        if graph[i][j]==0 and visited[i][j]==0:
            cnt+=1
            visited[i][j] =1
            a.append(1)
            q.append((i,j))
            while q:
                x, y = q.popleft()                
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if nx >= 0 and nx < m and ny >= 0 and ny < n and graph[nx][ny]==0 and visited[nx][ny] ==0:
                        visited[nx][ny]=1
                        a[cnt-1] += 1
                        q.append((nx,ny))

print(cnt)
print(*sorted(a))