백준 2583 영역 구하기 Python 3

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

2583번: 영역 구하기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2583.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
sys.setrecursionlimit(10001)
def dfs(x, y):
    global answer
    answer += 1
    for ddx, ddy in zip(dx, dy):
        nx, ny = x+ddx, y+ddy
        if 0 <= nx <N and 0 <= ny < M and not paper[ny][nx] and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny)

input = sys.stdin.readline
M, N, K = map(int, input().split())
paper = [[0]*N for _ in range(M)]
for _ in range(K):
    sx, sy, ex, ey = map(int, input().split())
    for x in range(sx, ex):
        for y in range(sy, ey):
            paper[y][x] = 1

visit = [[0]*N for _ in range(M)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = 0
area = 0
result = []
for y in range(M):
    for x in range(N):
        if visit[y][x] + paper[y][x] == 0:
            answer = 0
            visit[y][x] = 1
            dfs(x, y)
            result.append(answer)
            area += 1
print(area)
result.sort()
for r in result:
    print(r, end=' ')

---

풀이 과정

풀이 시간 31분

import sys
sys.setrecursionlimit(10001)
input = sys.stdin.readline

def dfs(x, y):
    #영역의 넓이 카운팅
    global answer
    answer += 1
    
    #인접한 4방향 탐색
    for ddx, ddy in zip(dx, dy):
        nx, ny = x+ddx, y+ddy
        #영역 안에 있으면서 빈 칸이고 이전에 방문하지 않은 칸이라면, 방문한다
        if 0 <= nx < N and 0 <= ny < M and not paper[ny][nx] and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny)

#입력 받아오기
M, N, K = map(int, input().split())
paper = [[0]*N for _ in range(M)]
for _ in range(K):
    sx, sy, ex, ey = map(int, input().split())
    for x in range(sx, ex):
        for y in range(sy, ey):
            paper[y][x] = 1

#영역 방문 처리
visit = [[0]*N for _ in range(M)]

#좌 상 우 하
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

#각 영역의 넓이
answer = 0
#영역 개수
area = 0
#영역의 넓이들을 담을 배열
result = []

for y in range(M):
    for x in range(N):
    	# (x, y) 칸이 이전에 방문한 적 없으면서 빈 칸인 경우, dfs 탐색 시작
        if visit[y][x] + paper[y][x] == 0:
            answer = 0
            visit[y][x] = 1
            dfs(x, y)
            result.append(answer)
            area += 1
print(area)
result.sort()
for r in result:
    print(r, end=' ')

#시간복잡도 = O(V+E), 공간복잡도 = O(n)