풀이
색종이 문제의 어려운 버전이다. 처음엔 좌표 최대 최소값을 비교해서 둘레만 구해주면 될 줄 알았는데 겹치지 않을 수도 있고 중간에 구멍이 뚫려있을 경우 그 둘레까지 구해야했기 때문에 다른 방법이 필요했다.
BFS 를 통해 경계선을 만날때마다 ans 를 1 씩 더해주다 보면 둘레의 길이를 알 수 있다.
먼저 100 x 100 의 도화지를 구현해 줄 때 모서리에 색종이가 배치될 것을 감안하여 102 x 102 도화지를 선언해준다.
한 칸씩 여유가 있어야 BFS 탐색을 할 때 경계선을 탐색할 수 있기 때문이다.
이후 입력받은 값에 따라 색종이가 배치된 지역을 1 로 바꿔준 후 전역을 탐색하며 BFS 를 수행해준다.
색종이가 탐색된 지점에서 BFS 를 실행시키면 해당 색종이의 영역을 전체적으로 탐삭하며 경계선에 닿을 때 마다 ans 값이 올라간다.
경계선의 값은 결국 둘레의 길이가 되기 때문에 해당 색종이 영역을 모두 탐색했을 경우 그 색종이 영역의 둘레를 구한 것이다.
리턴받은 값을 answer 에 더해준 후 아직 탐색되지 않은 색종이 영역을 찾아 위를 반복한다.
소스코드
# 색종이 - 2
from collections import deque
import sys
input = sys.stdin.readline
def bfs(i, j):
q = deque()
q.append((i, j))
visited[i][j] = 1
ans = 0
while q:
x, y = q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < 102 and 0 <= ny < 102 and visited[nx][ny] == 0:
if board[nx][ny] == 1:
q.append((nx, ny))
visited[nx][ny] = 1
else:
ans += 1
return ans
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
board = [[0] * 102 for _ in range(102)]
visited = [[0] * 102 for _ in range(102)]
answer = 0
for _ in range(int(input())):
x, y = map(int, input().split())
for i in range(x+1, x+11):
for j in range(y+1, y+11):
board[i][j] = 1
for i in range(1, 102):
for j in range(1, 102):
if board[i][j] == 1 and visited[i][j] == 0:
answer += bfs(i, j)
print(answer)