백준2583(파이썬) - 영역 구하기

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

2583번: 영역 구하기

• 이 문제는 중요한점이 2차원 배열 형태가 우리가 아는 방향이 아닌 그래프처럼 생각했을 때의 2차원 배열로 바꿔서 어떻게 푸느냐가 중요한 문제였다. 그래서 [m-y2,x1,n-y1-(n-m),x2] 이런식으로 우리가 아는 2차원 배열형태가 되도록 좌표를 변환해주었다.
•  그 다음에는 dfs를 사용했다. dfs를 사용해야 어디까지 연결되어있는지, 그리고 개수는 몇개인지 알 수 있다고 판단했다.
• 처음에는 영역의 개수를 0이 10000개인 리스트에 값을 더해서 받아준다음 set을 이용해 중복을 없애고 출력하였는데 생각해보니까 영역개수가 같은 영역일 경우에도 set을 통해 중복이 없어지는 문제가 생겼다.
• 주석 처리 된 부분은 처음에 짰던 코드와 논리적으로는 같은 코드인데 반례를 찾기 위해 방법을 이것저것 해본 코드이다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

dx = [1,-1,0,0]
dy = [0,0,1,-1]
def dfs(x,y):
    global num
    num += 1
    graph[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx > -1 and nx < m and ny > -1 and ny < n:
            if graph[nx][ny] == 0:
                dfs(nx,ny)
    
    """ if x <= -1 or x > m-1 or y <= -1 or y > n-1:
        return
    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1) 
        dfs(x, y-1) """
        
    

m,n,k = map(int,input().split())
graph = [[0]*n for _ in range(m)]
data = []
# 아래 코드가 그래프를 우리가 아는 그래프로 변환하는 과정
for i in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    data.append([m-y2,x1,n-y1-(n-m),x2]) #이 코드로 바꿔서 변환해준다.
for i in range(len(data)):
    for j in range(data[i][0],data[i][2]):
        for k in range(data[i][1],data[i][3]):
            graph[j][k] = 1
""" for i in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    for y in range((m-y2),(m-y1),1):
        for x in range(x1,x2,1):
            graph[y][x] = 1 """

#분리된영역의 개수들을 담을 list
numlist = []


for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
            num = 0
            dfs(i,j)
            numlist.append(num)
print(len(numlist))
for i in sorted(numlist):
    print(i,end=' ')