백준 파이썬 2583번 : 영역 구하기 풀이

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

2583번: 영역 구하기

영역이 주어지고, 갈 수 없는 영역이 주어졌을 때, 갈 수 있는 영역의 개수를 구하는 문제다. 

0,0에서 시작해서 BFS(너비 우선 탐색)을 동서남북 네 방향으로 실행하고,

한 칸 이동할 때마다 카운트를 더해주다가, 더 이상 갈 수 있는 영역이 없어졌을 때 카운트를 답에 저장해주면 된다. 

 

1. 사각형의 세로 길이는 m, 가로 길이는 n, 갈 수 없는 영역의 개수는 k개다 

2. 방문한 곳을 나타내기 위해 visited를 m*n으로 생성해준다 

3. 갈 수 없는 영역을 입력받아서 visited를 1로 바꿔준다 

4. BFS 탐색 

    1. 모든 영역 중, 방문하지 않은 곳에 대해서 탐색을 시작한다 

    2. 방문한 곳으로 표시해주고, 카운트를 1로 설정한다 

    3. 큐에 좌표를 넣어준다 

    4. 큐에 저장된 좌표의 동서남북 네 방향에 대해 동일한 작업을 수행하고, 탐색이 끝나면 카운트를 answer에 저장해준다

 

m, n, k = map(int,input().split()) #세로, 가로, 영역의 개수 
visited = [[0]*n for _ in range(m)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
answer = [] 
for _ in range(k):
    a,b,c,d = map(int,input().split())
    for i in range(b,d):
        for j in range(a,c):
            visited[i][j] = 1 
for i in range(m):
    for j in range(n):
        if visited[i][j] == 0:
            cnt = 1
            visited[i][j] = 1
            que = [[i,j]]
            while que:
                x,y = que[0][0], que[0][1]
                del que[0]
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<m and 0<=ny<n and visited[nx][ny] == 0:
                        visited[nx][ny] = 1 
                        cnt += 1 
                        que.append([nx,ny])
            answer.append(cnt)
print(len(answer))
answer.sort()
print(*answer)

<참고>

https://pacific-ocean.tistory.com/263

[백준] 2583번(python 파이썬)