[백준] 2583번: 영역 구하기 - 파이썬/python

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

2583번: 영역 구하기

접근 방식

- 고립된 영역 접근 방식 고민

- 방문 처리 방법 (visited 리스트 or 그래프 직접 표기) 및 시점

- count 시

 

코드 풀이

from collections import deque

m, n, k = map(int, input().split()) # 세로 길이, 가로 길이, 정사각형 수
graph = [[0]*m for _ in range(n)]

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(x1, x2):
        for j in range(y1, y2):
            graph[i][j] = 1 # x, y # 직사각형 내부는 모두 칠해줌
            
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
que = deque()

def bfs(graph, p, q):
    que.append([p, q])
    cnt = 0 # 초기 cnt
    
    while que:
        x, y = que.popleft() # popleft하면서
        graph[x][y] = 1 # 방문하고
        cnt += 1 # 세어줌
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0 <= ny < m and graph[nx][ny] == 0: # 새로운 좌표가 영역 안에 있고 직사각형 외부라면
                que.append([nx, ny])
                graph[nx][ny] = 1 # 중복 탐색이 일어나지 않도록 이 단계에서도 방문표시             
    return cnt

results = []
for i in range(m): # y
    for j in range(n): # x
        if graph[j][i] == 0:
            results.append(bfs(graph, j, i)) # 한번 bfs에 들어가면 해당 고립영역은 모두 탐색하고 나옴
            
print(len(results)) # 고립 영역의 갯수
for i in sorted(results):
    print(i, end = ' ') # 고립 영역의 크기 오름차순 출력

고립된 영역이 형성될 때, 해당 영역의 개수를 구하거나, 영역의 넓이를 구해야 풀 수 있는 문제의 경우는 bfs로 풀 수 있는 전형적인 문제입니다. 영역의 속성을 표현할 수 있는 그래프를 형성, 방문 처리 방식을 고민하고, x, y를 기준으로 nx, ny를 상하좌우로 탐색해주며 bfs 함수에서 활용할 수 있습니다. bfs 함수의 경우 queue 자료형을 활용하여 popleft 처리하며 count 작업을 진행함에 용이합니다.

 

오답 이유

- nx, ny를 구한 이후 que에 넣어 주고 방문 처리 (graph[nx][ny] = 1)을 해주지 않아 오답이 발생했습니다. que에 순차적으로 여러 개의 [x, y]가 들어가 있을 때, 미처 popleft 작업을 해주기 전에 중복 탐색이 일어날 가능성이 있기 때문입니다.

- 또한 if 0<= nx < n and 0 <= ny < m and graph[nx][ny] == 0: 부분에서 graph[x][y]로 오타가 발생하여, 새로운 x, y 좌표인 nx, ny를 그래프상에서 고려해주지 못했습니다.