[Boj/백준] 2583 Python

문제출처: https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

 

1. 문제 접근 방식

bfs로 풀기 위해 그래프를 숫자로 나타내려고 했고

0으로 초기화시킨 그래프에

직사각형 좌표에 따라서 1을 찍어줬다.

 

 

2. 내가 푼 코드

import sys
from collections import deque

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 1

    cnt = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or nx>=m or ny<0 or ny>=n:
                continue
            if graph[nx][ny] == 0:
                cnt+=1
                queue.append((nx,ny))
                graph[nx][ny] = 1
    return cnt

total = 0
result = []

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

m,n,k = map(int,sys.stdin.readline().split())

graph = []
for _ in range(m):
    graph.append([0]*n)

for _ in range(k):
    arr = list(map(int,sys.stdin.readline().split()))
    for i in range(m-arr[3],m-arr[1]):
        for j in range(arr[0],arr[2]):
            graph[i][j] = 1


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

print(total)

result.sort()
print(' '.join(map(str,result)))

 

 

3. 결과 및 느낀점

문제를 제대로 안 읽어서 실수를 했다. 0 => 1로 카운팅 해줘야하는데 반대로 해줘서 애를 먹었다.

실수를 하지말자...