[CodeUp] 4572번 : 영역 구하기 (Python)

[CodeUp] 4572번 : 영역 구하기 (Python)

 

 

목차

 

 

  

https://codeup.kr/problem.php?id=4572&rid=0 

영역 구하기

  

Python

 

방법 1 - 메모리 29204 / 시간 30 / 코드 길이 645B

 

DFS로 시행했는데.... 7번째 테스트 케이스에서 에러가 나서 시간을 왕창보냄.....

이때 sys.setrecursionlimit을 써주면 됨

 

import sys
sys.setrecursionlimit(10000)

m,n,k = list(map(int, input().split()))
rec=[[0]*n for _ in range(m)]

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

def dfs(x, y):
    if x<0 or x>n-1 or y<0 or y>m-1:
        return 0

    if rec[y][x]:
        return 0

    rec[y][x] = 1
    return 1 + dfs(x-1, y) + dfs(x+1, y) + dfs(x, y-1) + dfs(x, y+1)

cnt_s = []
for i in range(m):
    for j in range(n):
        if rec[i][j] == 0:
            cnt_s.append(dfs(x=j, y=i))

print(len(cnt_s))
print(*sorted(cnt_s))

 

방법 2 - 메모리 29484 / 시간 28 / 코드 길이 699B

 

다른 DFS 방법

 

import sys
sys.setrecursionlimit(10000)

m,n,k = map(int, input().split())
rec=[[0]*n for _ in range(m)]

for _ in range(k):
    x1,y1,x2,y2 = map(int, input().split())
    # i : row, y
    # j : col, x
    # matrix[row or y][col or x]
    for i in range(y1, y2):
        for j in range(x1, x2):
            rec[i][j] = 1

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

def dfs(x, y, cnt):
    rec[y][x] = 1
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if 0 <= nx < n and 0 <= ny < m and rec[ny][nx] == 0:
            cnt = dfs(nx,ny,cnt+1)
    return cnt

cnt_s = []
# m, i : row, y
# n, j : col, x
# matrix[row or y][col or x]
for i in range(m):
    for j in range(n):
        if rec[i][j] == 0:
            cnt_s.append(dfs(x=j, y=i, cnt=1))

print(len(cnt_s))
print(*sorted(cnt_s))

"""
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2
"""

 

 

 

방법 3 - 메모리 30308 / 시간 32 / 코드 길이 1023B

 

BFS를 사용한 방법 

 

from collections import deque

m,n,k = map(int, input().split())
rec=[[0]*m for _ in range(n)]
visit = [[False] * m for _ in range(n)]

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

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

def bfs(x, y):
    cnt = 1
    q = deque()
    q.append([x,y])
    visit[x][y] = True

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if nx<0 or nx>n-1 or ny<0 or ny>m-1:
                continue

            if rec[nx][ny] == 0 and visit[nx][ny] == False:
                visit[nx][ny] = True
                q.append([nx,ny])
                cnt += 1
    return cnt

cnt_s = []
for i in range(n):
    for j in range(m):
        if rec[i][j] == 0 and visit[i][j] == False:
            cnt_s.append(bfs(i, j))

print(len(cnt_s))
for i in sorted(cnt_s):
    print(i, end=' ')

 

 

 

0000