BOJ 2583

Input

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다.

둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

• 좌표로 주어지는 직사각형 외의 공간을 구하는 문제이므로, 주어지는 직사각형의 영역은 1 로 표기해둔다.
• 이 때, 좌표로 직사각형이 주어지므로 한 칸에 해당하는 좌표와 이를 구분해야 한다.
• 즉, 한 칸의 영역은 끝 좌표-1 에 해당한다.

m, n, k = map(int, sys.stdin.readline().split())
board = [[0]*(n) for _ in range(m)]
for _ in range(k):
  x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
  x2 -= 1
  y2 -= 1
  for x_idx in range(x1, x2+1):
    for y_idx in range(y1, y2+1):
      board[y_idx][x_idx] = 1

Default

import sys
sys.setrecursionlimit(1000000)

DFS

• 연속되는 공간을 찾을 때, 위/아래/양 옆을 체크하므로 dir 을 미리 세팅한다.

• 출력해야 하는 값이 count 와 영역 이므로 이 둘에 해당하는 변수를 생성한다.

• 모든 보드의 칸을 돌면서 0 인 경우 해당 영역의 넓이를 구하고 count+1 을 해야 하므로 가장 바깥쪽이자 전체를 도는 for문을 생성한다.

  • 0임을 체크하면, 다시 이 영역을 count하면 안 되므로 1로 세팅하고, 해당 영역부터 넓이를 체크해야 하므로 area는 1로 초기화, 그리고 dfs를 돈다.
  • area를 global 로 설정하여 해당 변수를 result에 append 하여 이후 출력값을 sort 한다.
  • 또한, 연속된 0 값을 체크하여 영역을 세는 것이므로 count++ 을 수행한다.

  for y in range(m):
    for x in range(n):
      if board[y][x] == 0:
        board[y][x] = 1
        area = 1
        dfs(y, x)
        result.append(area)
        count += 1

• 연속된 영역을 파악하기 위해 dfs를 돈다.

  • 미리 생성해 둔 dir에 따라 연속된 넓이를 체크하고,
  • 이 때 범위 내의 값일 경우, 위와 동일하게 칸을 1로 세팅, 넓이를 +1하고 dfs를 이어서 수행한다.

  def dfs(dy, dx):
    global area
  
    for dd in dir:
      x = dd[0] + dx
      y = dd[1] + dy
  
      if 0 <= x < n and 0 <= y < m:
        if board[y][x] == 0:
          board[y][x] = 1
          area += 1
          dfs(y, x)

Output

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다.

둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

int 배열 값을 str으로 하나씩 출력하는 법

' '.join(map(str, arr)) 를 통해 1 7 13 과 같이

int 값을 str로 mapping하고 한 칸 띄어쓰기를 join 한다.

런타임 에러가 뜰까봐 sys를 이용하는데, 알고리즘은 다 맞아놓고 자꾸 출력 형식에서 틀린다… 바보야…!!!!!!

result.sort()
sys.stdout.write(str(count))
print()
sys.stdout.write(' '.join(map(str, result)))