백준 2583 파이썬

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

2583번: 영역 구하기

DFS로 풀이했다.

나 근데 가로 세로가 아직 헷갈린다;;

아이디어는 다음과 같다.

n = 7, m = 5 사이즈의 2차원 배열 (= 그래프) 가 있다고 생각하면, 각 칸을 모두 0으로 초기화 시킨다

입력되는 직사각형 부분에 해당하는 칸들은 2차원 배열에서 1로 표시한다. 1은 이미 방문된 노드라는 의미이다. 

그후 전체 2차원 배열을 이중 for문으로 하나씩 칸의 값을 체크하면서 0 인 경우, 아직 방문하지 않은 즉 직사각형이 없는 칸이므로 그 칸에서부터 dfs를 실행해준다. 

재귀함수인 dfs를 마지막으로 마칠 때 칸들의 개수인 temp 변수를 return 해준다.그리고 다음 칸에서 dfs를 실행시키기 전에 다시 temp를 0으로 초기화 시켜준다 

실수했던 점은 dfs에서 array[x][y] 칸부터 세어야 하는데 엉뚱한 곳에서 카운트 했던 점,

그리고 이중 for 문에서 높이에 해당하는 부분이 바깥의 loop 인데 실수한 점.. 이다 

# 2583 영역 구하기
import sys
sys.setrecursionlimit(10000)

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

for _ in range(k):
    a, b, c, d = map(int, input().split())
    for i in range(b, d):
        for j in range(a, c):
            array[i][j] = 1 # 직사각형

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
result = []
temp = 0
def dfs(x, y):
    global temp
    array[x][y] = 1
    temp += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and array[nx][ny] == 0:
            dfs(nx, ny)
    return temp

for i in range(m):
    for j in range(n):
        if array[i][j] != 1:
            temp = dfs(i, j)
            if temp != 0:
                result.append(temp)
                temp = 0

result.sort()
print(len(result))
for i in result:
    print(i, end=' ')

 

어쩌면 BFS가 역시 구현은 조금 더 쉬울지도..? 하면서 

BFS로 풀이해보았다.

# 2583 영역 구하기
from collections import deque

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

for _ in range(k):
    a, b, c, d = map(int, input().split())
    for i in range(b, d):
        for j in range(a, c):
            array[i][j] = 1 # 직사각형

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

def bfs(x, y):
    queue = deque()
    array[x][y] = 1
    queue.append((x,y))
    count = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (0 <= nx < m) and (0 <= ny < n) and array[nx][ny] == 0:
                array[nx][ny] = 1
                queue.append((nx, ny))
                count += 1
    return count


for i in range(m):
    for j in range(n):
        if array[i][j] == 0:
            result.append(bfs(i, j))

result.sort()

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