[Python] 2583번 영역 구하기

✏️ 문제

 

문제 파악

입력값은 점을 기준으로 주니까 배열로 구현하려 할 때 조금 헷갈렸다. 

그래서 아래와 같이 그림 그리니 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값은 그대로, 오른쪽 위 꼭짓점의 x, y좌표값은 -1씩하면 됐었다.

 

직사각형이 있는 영역은 방문하면 안되는 영역이므로 -1로 표시했다.

 

아 그리고 이 문제는 DFS로 풀었을 때 재귀를 사용하면 RecursionError가 발생하므로 나는 재귀 대신 스택을 사용해서 풀었다.

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

import sys
input = sys.stdin.readline

m, n, k = map(int, input().split())
graph = [[0] * n for __ in range(m)]
visited = [[0] * n for __ in range(m)]
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
areas = []
cnt = 0

for _ in range(k):
  l_x, l_y, r_x, r_y = map(int, input().split())
  for i in range(l_x, r_x):
    for j in range(l_y, r_y):
      graph[j][i] = -1
      visited[j][i] = -1

def dfs(x, y):
  stack = [(x, y)]
  area_size = 0

  while stack:
    x, y = stack.pop()

    if visited[x][y] == 0:
      visited[x][y] = 1
      area_size += 1

      for i in range(4):
        dx = x + d[i][0]
        dy = y + d[i][1]

        if 0 <= dx < m and 0 <= dy < n and visited[dx][dy] == 0:
          stack.append((dx, dy))

  return area_size

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

areas.sort()
print(cnt)
print(" ".join(map(str, areas)))

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS