풀이
색종이 문제의 어려운 버전이다. 처음엔 좌표 최대 최소값을 비교해서 둘레만 구해주면 될 줄 알았는데 겹치지 않을 수도 있고 중간에 구멍이 뚫려있을 경우 그 둘레까지 구해야했기 때문에 다른 방법이 필요했다.
BFS 를 통해 경계선을 만날때마다 ans 를 1 씩 더해주다 보면 둘레의 길이를 알 수 있다.
먼저 100 x 100 의 도화지를 구현해 줄 때 모서리에 색종이가 배치될 것을 감안하여 102 x 102 도화지를 선언해준다.
한 칸씩 여유가 있어야 BFS 탐색을 할 때 경계선을 탐색할 수 있기 때문이다.
이후 입력받은 값에 따라 색종이가 배치된 지역을 1 로 바꿔준 후 전역을 탐색하며 BFS 를 수행해준다.
색종이가 탐색된 지점에서 BFS 를 실행시키면 해당 색종이의 영역을 전체적으로 탐삭하며 경계선에 닿을 때 마다 ans 값이 올라간다.
경계선의 값은 결국 둘레의 길이가 되기 때문에 해당 색종이 영역을 모두 탐색했을 경우 그 색종이 영역의 둘레를 구한 것이다.
리턴받은 값을 answer 에 더해준 후 아직 탐색되지 않은 색종이 영역을 찾아 위를 반복한다.
소스코드
References