2583 - 영역 구하기

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

 

 

 

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

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

a = [list(map(int, input().split())) for _ in range(k)]

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

visited = [[0] * m for _ in range(n)]

for i in range(k):
    s = a[i]
    for i in range(n):
        for j in range(m):
            if s[0] <= i < s[2] and s[1] <= j < s[3]:
                visited[i][j] = 1

s_list = []
tmp_list = []

def dfs(x, y):
    visited[x][y] = 1
    tmp_list.append(1)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if visited[nx][ny] == 0:
            dfs(nx, ny)

for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            dfs(i, j)
            s_list.append(sum(tmp_list))
            tmp_list.clear()

s_num = len(s_list)
print(s_num if s_num > 0 else 1)
print(*sorted(s_list))

 

1. 풀이 알고리즘 : DFS(선택), BFS, 인접 리스트 etc

 

2. 핵심 아이디어

   2-1. K 개의 사각형 영역을 먼저 방문처리

   2-2. 방문되지 않은 영역을 깊이우선탐색하여 영역의 넓이과 갯수를 구함

   2-3. 다른 풀이 방법 :

K 개의 사각형 영역을 먼저 방문하지 않고, 방문되어야할 영역을 한번에 걸러서 처리하면 더 빠를 것으로 생각함

BFS로도 풀어보면 좋을 것 같음

 

3. 어려웠 던 부분

  3-1. (0,0) 의 위치가 왼쪽 하단에 있어서 Matrix를 만들 때 너무 헷갈려서, n과 m을 거꾸로 넣어버림

  3-2. 탐색 시 영역의 넓이를 누적하는 로직을 스택 함수에 넣었더니, 스택을 빠져나오면서 값이 원복되었음

-> tmp_list에 1씩 담아서 나중에 s_list에 담기 전에 sum()을 통해 누적합 하여 해결함

-> 다른 방법이 있는지 탐구 필요

 

4. 코드 개선

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

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

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

a = [list(map(int, input().split())) for _ in range(k)]

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

visited = [[0] * m for _ in range(n)]

for i in range(k):
    s = a[i]
    for i in range(n):
        for j in range(m):
            if s[0] <= i < s[2] and s[1] <= j < s[3]:
                visited[i][j] = 1

s_list = []

def dfs(x, y):
    visited[x][y] = 1
    ret = 1 # dfs 들어갈때마다 1을 return하기위해서 ret = 1로 둠, 가중치가 2면 ret = 2 로 해야함
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if visited[nx][ny] == 0:
            ret += dfs(nx, ny) # 모든 dfs 의 결과값인 return ret을 ret에 더한다
    return ret

for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            s_list.append(dfs(i, j))

s_num = len(s_list)
print(s_num if s_num > 0 else 1)
print(*sorted(s_list))

 

1. s_list에 담는 시점에 dfs(i, j)를 호출

2. ret = 1인 이유는, 가중치가 1이기 때문임 -> dfs 깊이를 들어간 만큼 return ret (=1) 을 계속 반환

3. 반환한 값들을 ret += dfs(nx, ny)에서 모두 더함 -> 빈 영역의 넓이 = 사각형의 갯수

4. 다 더한 후에 s_list.append(dfs(i, j))를 통하여, 빈 영역의 넓이를 담는다.

5. 빈 영역이 총 3개 이고 각각 1, 7, 13 이다