[Python][백준/BOJ] 2583번 : 영역 구하기

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

2583번: 영역 구하기

 

내 코드

import sys
input = sys.stdin.readline
from collections import deque

m, n , k = map(int, input().split())
graph = [[0]*(n) for _ in range(m)]

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1,y2):
        for j in range(x1, x2):
            graph[i][j] +=1

def bfs(y, x):
    cnt2=1
    q = deque()
    q.append((y, x))
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while q:
        y,x = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<= nx < n and 0 <= ny < m:
                if graph[ny][nx] == 0: 
                    graph[ny][nx] =1
                    q.append((ny, nx))
                    cnt2 +=1
    return cnt2

arr =[]   
cnt =0
for i in range(m):
    for j in range(n):
        if graph[i][j] ==0:
            graph[i][j] +=1
            cnt+=1
            arr.append(bfs(i, j))
            
arr.sort()
print(cnt)
print(' '.join(map(str, arr)))

 

코드 리뷰

BFS

이 문제를 BFS로 풀었던 이유는, 그래프의 모든 부분을 하나하나 다 지나면서 이어져 있는 부분을 체크할 예정이었기 때문이다. 

 

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1,y2):
        for j in range(x1, x2):
            graph[i][j] =1

먼저 입력값을 차례대로 받으면서, 입력받은 칸 이내에 있는 구간은 숫자로 채워져있다는 의미이므로 1로 채워주었다. 원래는 +=1 을 하며 숫자로 받아야 하는 것 같지만, 어차피 해결하는 과정에서 0과 0이 아닌 것으로 구분하여 답을 구할 것이기 때문에 이렇게 구했다. 

 

def bfs(y, x):
    cnt2=1
    q = deque()
    q.append((y, x))
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while q:
        y,x = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<= nx < n and 0 <= ny < m:
                if graph[ny][nx] == 0: 
                    graph[ny][nx] =1
                    q.append((ny, nx))
                    cnt2 +=1
    return cnt2

그리고 BFS는 기본적인 구조를 갖추며 구성했다. 이때 그래프 자체의 y와 x의 크기가 다르기 때문에 반드시 y와 x를 잘못 쓰지 않았나 확인하고 또 확인해야 한다!

 

for i in range(m):
    for j in range(n):
        if graph[i][j] ==0:
            graph[i][j] +=1
            cnt+=1
            arr.append(bfs(i, j))

마지막으로 그래프를 전체적으로 a부터 z까지 다 훑어보다가 만약 0인 곳이 있으면, 그 곳을 체크해줘야 한다. 그래서 0인지를 체크해주고, 만약 한다면 bfs를 실행한 후 1을 추가해주면 된다.

오랜만에 접한 bfs문제였는데 비교적 간단하게 풀 수 있었다.