[ BOJ 2583 ] 영역 구하기(Python)

문제

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

입력이.. 더러웠다.. 그리고 내 풀이도.. ,.
진심 넘 더럽게 풀어서 다시 풀어야 할 것 같다.

문제 풀이

우선 입력을 받아서 maps 그래프를 만들어주었다.
그래프는 0으로 초기화 해주고, 직사각형의 범위만 1로 바꿨다.
m = 행의 개수, n = 열의 개수, k = 직사각형 수

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

maps = [[0 for _ in range(n)] for _ in range(m)]
dst = defaultdict(list)

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

상하좌우로 이동하면서 직사각형이 아닌 구역을 체크한 뒤 dst 인접 리스트로 연결해주었다.

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

for x, rows in enumerate(maps):
    for y, char in enumerate(rows):
        if char == 0:
            dst[(x, y)].append((x, y))
            for t in range(4):
                nx = dx[t] + x
                ny = dy[t] + y
                if (0 <= nx < m and 0 <= ny < n and maps[nx][ny] == 0):
                    dst[(x, y)].append((nx, ny))

dfs 함수로 이동할 때마다 cnt에 1씩 더해줬고 0을 1로 바꾸어주었다. 계속 이동하다가 더 이상 이동할 수 없으면 cnt를 반환해주었다.
만약 이미 방문한 곳이면 False를 반환해주었다.

def dfs(x, y):
    global cnt

    cnt += 1
    if maps[x][y] == 0:
        maps[x][y] = 1

        for (nx, ny) in dst[(x, y)]:
            if maps[nx][ny] == 0:
                dfs(nx, ny)
    else:
        return False
    return cnt

False가 아닌 cnt가 반환될 때마다 ground 구역의 수를 1씩 증가시켰다.
cnt는 result 리스트에 추가해주었다.

ground = 0
result = []

for x, y in dst:
    cnt = 0
    answer = dfs(x, y)
    if answer:
        ground += 1
        result.append(answer)

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

코드

import sys
from collections import defaultdict
sys.setrecursionlimit(100001)
input = sys.stdin.readline

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

maps = [[0 for _ in range(n)] for _ in range(m)]
dst = defaultdict(list)

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

# for row in maps:
#     print(row)
# print()


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

for x, rows in enumerate(maps):
    for y, char in enumerate(rows):
        if char == 0:
            dst[(x, y)].append((x, y))
            for t in range(4):
                nx = dx[t] + x
                ny = dy[t] + y
                if (0 <= nx < m and 0 <= ny < n and maps[nx][ny] == 0):
                    dst[(x, y)].append((nx, ny))

# print(dst)

cnt = 0

def dfs(x, y):
    global cnt

    cnt += 1
    if maps[x][y] == 0:
        maps[x][y] = 1

        for (nx, ny) in dst[(x, y)]:
            if maps[nx][ny] == 0:
                dfs(nx, ny)
    else:
        return False
    return cnt

ground = 0
result = []

for x, y in dst:
    cnt = 0
    answer = dfs(x, y)
    if answer:
        ground += 1
        result.append(answer)

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