영역 구하기 - 실버 1 (백준, bfs)

 

from collections import deque

M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]


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


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

result = []

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

print(len(result))
print(*sorted(result))

pypy3로 해야 실행이 된다. 원하지 않는다면 sys를 사용하자.

 

이 문제는 풀지 못했다. 그리고 풀지 못한 이유는 단 하나

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

이 부분 때문이다. 범위가 주어지는 것에 대한 생각을 해보지 않았다는 것이 참 아쉽다.

 

하지만 이번 문제를 통해서 다음에 주어진 좌표의 범위를 알아야하는 경우를 놓치지 않겠다. 

 

기억하고 사용하자.