BOJ 2567 - 색종이 - 2

풀이

---

색종이 문제의 어려운 버전이다. 처음엔 좌표 최대 최소값을 비교해서 둘레만 구해주면 될 줄 알았는데 겹치지 않을 수도 있고 중간에 구멍이 뚫려있을 경우 그 둘레까지 구해야했기 때문에 다른 방법이 필요했다.

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)

References

---

• BOJ 2567 - 색종이 - 2