[백준2583&파이썬] 좌표평면을 배열로 표현하는 방법

# 문제

백준2583 영역구하기 파이썬 풀이

2583번: 영역 구하기

 

# 코드

import sys
from collections import deque


M,N,K = map(int, sys.stdin.readline().split())
# M 행 , N 열

board = [ [False] * N for i in range(M)]

def printBoard() :
  for i in range(M) :
    print(board[i])

dirs = [
  (-1,0),(0,1),(1,0),(0,-1)
  ]

for _ in range(K) :
  x1,y1,x2,y2 = map(int, sys.stdin.readline().split())
  # 0 2 4 4
  for i in range(y1, y2):
    for j in range(x1, x2):
      board[i][j] = True

# printBoard()

cnt = 0
sizes = list()

for row in range(M) :
  for col in range(N) :
    size = 1
    if board[row][col] == False :
      cnt +=1
      # bfs로 세는거 시작해야함
      dq = deque()
      dq.append( (row,col))
      board[row][col] = True # 방문처리
      while len(dq) != 0 :
        cur = dq.popleft()

        for dir in dirs :
          next = ( cur[0] + dir[0], cur[1] + dir[1])

          # 범위 안에 드는지 확인
          if 0<= next[0] < M and 0<= next[1] < N :
            # 방문했는지 확인하기
            if board[next[0]][next[1]] == False :
              # 방문 및 넓이 카운트 하기
              board[next[0]][next[1]] = True
              size +=1
              dq.append(next)
      sizes.append(size)

print(cnt)
sizes.sort()
for _ in range(len(sizes)) :
  print(sizes[_],end=" ")

 

# 풀이

## 탐색 시작지점과 방문표시의 갯수 세기

BFS를 이용하여 푸는 전형적인 방법이다. BFS를 통한 풀이를 해봤다면 별다른 고민을 하지는 않아도 될 것 같다.

 

## 좌표평면을 배열로 나타내기

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

• 배열로 나타내는 row와 col은 시작지점이 왼쪽 위부터이다. 그러나 문제에서는 좌표평면이 주어졌고 시작지점이 왼쪽 아래서부터이다.
• 좌표는 0 2 4 4 와 같은 형태로 주어지고, 시작지점 (0,2) 마지막지점 (4,4)의 형태가 되고 이를 통해서 사각형을 칠할 수 있다.
• 나는 이 좌표평면의 시작점이 다르기 때문에 이를 맞추기 위해서 보정작업을 하려고 했다.
• 그러나 정확한 모양을 그리는게 아니라면 아래와 같이 반전된 모양으로 그대로 그릴 수 있다.

[False, False, False, False, True, True, False]
[False, True, False, False, True, True, False]
[True, True, True, True, False, False, False]
[True, True, True, True, False, False, False]
[False, True, False, False, False, False, False]

• 아래와 같이 코드를 작성하자

for _ in range(K) :
  x1,y1,x2,y2 = map(int, sys.stdin.readline().split())
  for i in range(y1, y2):
    for j in range(x1, x2):
      board[i][j] = True