[Python] 백준 2583번 영역 구하기 (DFS)

문제

풀이

DFS로 풀었다.

문제에 조금(?) 함정이 있는데, 바로 왼쪽 아래가 (0,0)이다. 한참 찾았다.

또한 직사각형 좌표를 왼쪽 아래, 오른쪽 위의 "꼭지점"좌표로 주기 때문에 왼쪽 아래의 좌표의 x,y 값은 포함,(이상) 오른쪽 위의 좌표의 x,y 값은 미 포함(미만) 이다.

하지만 왼쪽 위가 (0,0), 그리고 직사각형의 좌표를 왼쪽 위 기준으로 받아들이면 모눈종이 가운데를 기준으로 반전 시킨 것과 같다. 따라서 그냥 풀어도 답에는 이상이 없다.

import sys

sys.setrecursionlimit(100000)

def dfs(table, start, rectangle):

    count = 1

    x, y = start

    if x < 0 or y < 0 or x >= len(table[0]) or y >= len(table):

        return 0

    if table[y][x]:

        return 0

    for lx, ly, rx, ry in rectangle:

        if lx <= x and ly <= y and rx > x and ry > y:

            return 0

    table[y][x] = True

    UDLR = [[0, -1], [0, 1], [-1, 0], [1, 0]]

    for i in UDLR:

        dx = x+i[0]

        dy = y+i[1]

        count += dfs(table, (dx, dy), rectangle)

    return count

rectangle = []

m, n, k = map(int, input().split())

table = [[False for _ in range(n)]for _ in range(m)]

for i in range(k):

    rectangle.append(list(map(int, input().split())))

area = 0

width = []

for i in range(m):

    for j in range(n):

        temp = dfs(table, (j, i), rectangle)

        if temp != 0:

            area += 1

            width.append(temp)

print(area)

width.sort()

for i in width:

    print(i, end=' ')