넓이

• 넓이를 구할 때 가장 많이 하는 실수:
  • 사각형의 좌측 하단 (1,1), 우측 상단 (4,3) -> 그대로 0을 채우는 실수
    

---

• 점선 좌표에 따른 행렬 생각
  

---

• 해결 방법
  • 위와 같이 그림을 그리라고 할 때!
    • 이렇게 채워야함
  • 이렇게 Rect 객체를 만들어 관리하면, for문에서 매우 사용이 쉽다.

class Rect():
    def __init__(self, x, y):
        self.upper_left=(x,y)
        self.upper_right=(x,y+10)
        self.lower_left=(x+10,y)
        self.lower_right=(x+10,y+10)

rect_arr=[]
rect_arr[0]=(Rect(1,1))
rect_arr[1]=(Rect(5,10))
...

for k in range(0, len(rect_arr)):
    row=rect_arr[k].upper_left[0] # upper_left(x)
    col=rect_arr[k].upper_left[1] # upper_left(y)
    row_end=rect_arr[k].lower_right[0] # lower_right(x)
    col_end=rect_arr[k].lower_right[1] # lower_right(y)
    for i in range(row, row_end):
        for j in range(col, col_end):
            maps[i][j]=1

• 위 코드로 구현한 것은 아님 여튼, 콘솔로 그릴 수 있다.
• 그런데 이건 너무 느리다. 둘레를 구해서 $가로 * 세로$ 방식이 제일 빠르다.

---

1. 둘레

1-1. 둘레 구하기 기본

• 위와 같은 필터를 만들어서 외각에서 1 검출시 cnt++
  • 아래의 모습을 기억하자
    노란색 영역이 스캐너가 지나가면서 cnt 올리는 자리다.
    
    이런식으로 파고들어간 중복에서도 cnt를 잘 올릴 수 있다.

---

따라서, 제일 side 쪽에도 둘레를 구하려면 실제 row +2, 실제 col +2 로 배열을 선언한다.

---

1-2. 최외곽 둘레만 구하기

• Flood Fill과 비슷하지만 Python은 재귀를 할수 있으면 피할 것.
  • 원본 맵을 visited 없이, if map[nx][ny] == 0: map[nx][ny]=-1 로 체킹하면서 나아간다.
    
  • 

while Q:
    x, y = Q.popleft()
    for i in range(0,4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0 <= nx < row and 0 <= ny < col:
            if maps[nx][ny]==0:
                maps[nx][ny]=-1
                Q.append((nx,ny))
            elif maps[nx][ny] == 1:
                cnt+=1
print(cnt)

---

1-3. 백준 치즈

• https://www.acmicpc.net/problem/2638
  • 

Q=deque()
nQ=set()
maps[0][0]=-1 # visitied: -1
Q.append((0,0))
while Q:
    x,y=Q.popleft()
    for i in range(0,4):
        nx=x+dx[i]
        ny=y+dy[i]
        if (0<=nx<R) and (0<=ny<C):
            if (maps[nx][ny] == 0):
                maps[nx][ny]=-1 # visited: -1
                Q.append((nx,ny))
            elif (maps[nx][ny] >= 1):
                maps[nx][ny]+=1
                if maps[nx][ny] >= 3:
                    nQ.add((nx,ny)) # 따로 모아둠

• 여기까지 하면 2번 이상 터치한 것이 3 이상 인데, 이 값들은 다음 BFS에서 0으로 만들어야한다.
  그래서 위 코드의 nQ에 있는 좌표들을 0으로 만든다.
  나머지는 모두 1 처리한다.

while nQ:
    x,y=nQ.pop()
    if maps[x][y] >= 3:
        maps[x][y]=0
    else:
        maps[x][y]=1

• 

---

• 이후 다시 BFS로 돌아야 하기 때문에, min_RC, max_RC 값을 잘 조절해 -1->0으로 만들어 다시 탐색한다.

---

2. 넓이

• 1. 위에서 처럼 cnt++을 통해, 둘레를 구하여 $가로*세로$ 로 넓이를 구하는 방법
• 2. 주어진 정보를 토대로 $가로*세로$ 로 넓이를 구하는 방법
  • 
• 작은 직사각형 구하는 방법:

1. 무빙이 주어질 때
   
   이러한 무빙일 때가 작은 사각형을 만들 때임

---

3. 곂치기

---

원 내 사각형 갯수

• 원의 $1/4$내 사각형 갯수만 구한 후 $* 4$ 하면된다.
• 사각형 갯수는 '좌 상단 하나'만 들어가면 사각형 들어가는 것임
• 좌표의 길이가 원의 반지름 $r$ 내에 있으면 원에 포함된다.
  • 당연히 원의 반지름 $r$은 피타고라스의 정리로 구한다.
    • ${r^2=a^2+b^2}$