flood fill 핵심 트릭 - 사각형으로 둘러쌓인 연결요소의 둘레의 길이(연결요소 내부 영역을 찾는 방법)

5850번: Perimeter

 

100*100 들판에 1*1 건초를 n개 두는데 이 건초 n개는 연결되어있다.

 

즉 임의의 건초에서 상하좌우로 출발하면 다른 모든 건초로 도달할 수 있다

 

이 연결된 영역의 둘레를 구하고 싶다.

 

이때 건초 더미들이 감싸고 있는 내부 구멍이 있을 수 있는데 이 구멍들의 둘레는 계산하지 않는다

 

예를 들어 아래 그림은 둘레가 14이다.

 

X부분의 둘레는 계산하지 않는다

 

 

 

---------------------------------------------------------------------------------------------------------------------------------

 

건초더미 둘레를 구해야하는데 건초더미가 감싸는 내부 구멍을 어떻게 찾아야하느냐가 관건이다

 

(0,0)부터 BFS를 해야하나?

 

(0,0)이 건초일수도 있는데?

 

모든 점을 탐색해봐서 건초가 아닌 지점에서 BFS를 해봐야하나?

 

그 지점에서 BFS를 했을때 그 영역이 내부 영역이라고 어떻게 확신해?

 

확실하게 찾는 방법은 바로 둘레에 padding을 채우는것이다

 

크기가 100이지만 0부터 101까지로 배열을 잡으면, 좌표는 1~100으로만 주어지니까 그 둘레가 패딩으로 씌워진다

 

패딩 부분은 확실하게 건초더미 밖이므로, 이렇게 하면 (0,0)부터 시작해서 외부 영역을 채워나갈 수 있다

 

외부 영역을 찾는건 찾았다하는데, 둘레는 어떻게 구함?

 

건초더미는 2로 표시하고, (0,0)에서 BFS를 하면 외부영역이 1로 채워지는데,

 

아래 그림과 같아진다

 

그림을 잘 보면 뭔가 보인다

 

 

 

 

놀랍게도 2로 표시된 부분을 순회해서, 상하좌우를 탐색해가지고, 1로 표시된 부분의 개수를 세면 된다

 

그러면 내부 구멍은 0으로 표시되어있으니 자연스럽게 둘레에서 제외된다

 

특히 아래 파란부분은 중복된 부분이 있는데, 그거랑 상관없이 그냥 세줘도 된다는것을 확인할 수 있다

 

 

 

 

 

from collections import deque
from sys import stdin

n = int(stdin.readline())

maps = [[0]*(102) for _ in range(102)]
visited = [[0]*102 for _ in range(102)]

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())
    maps[y][x] = 1
    visited[y][x] = 2

queue = deque([(0,0)])

while queue:
    
    x,y = queue.popleft()

    for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:
        
        dx = x + a
        dy = y + b

        if dx >= 0 and dx <= 101 and dy >= 0 and dy <= 101:
            
            if visited[dy][dx] == 0:
                
                visited[dy][dx] = 1
                queue.append((dx,dy))

p = 0

for y in range(1,101):
    
    for x in range(1,101):
        
        if visited[y][x] == 2:
            
            for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + a
                dy = y + b

                if visited[dy][dx] == 1:
                    
                    p += 1

print(p)