[C++] 백준 2583번 영역 구하기

그래프 탐색 이론 문제.

백준에서 최근에 판에 색종이 올리고 남은 공간에 넓이를 구하는 문제가 있었는데, 그 문제를 푼게 도움이 많이 됐다.

어렵지 않게 풀 수 있는 문제

 

문제풀이

문제가 연결요소의 개수를 구하는 것을 물어보고 있다.

그리고 좌표를 알려주면서 해당 영역에 사각형이 붙여져 있다는 것을 알려준다.

좌표계를 <그림 1>처럼 나타내려면 조금 복잡해서, 편하게 위 아래로 뒤집은 형태로 구현해서 풀었다.

어차피 연결요소 개수는 달라지지 않을테니까.

 

101x101 짜리 배열을 하나 선언해서 입력받는 좌표에 따라서 해당 영역들에 이미 사각형이 있다는 것을 표시해주고,

표시되지 않은 곳에서 DFS를 해서 표시되지 않은 곳 끼리 한 영역이 되게 구현하면 된다.

 

좌표는 나같은 경우는 한 칸을 좌표 다음으로 보아서 (0, 2) -> (4, 4)를 (1, 3) -> (4, 4)로 보았다.

이렇게 하면 x의 범위가 4, 가로가 4이고 y의 범위가 2, 세로가 2인 사각형이 좌표에 그려지는 것이다.

 

이제 코드를 살펴보겠다.

사용한 STL과 변수

각 영역의 넓이를 담을 벡터 result를 사용하기 위해 vector STL을 사용했다.

result 벡터를 정렬하기 위해 sort 메서드를 사용하기 위한 algorithm STL을 사용했다.

그리고 모눈종이를 나타내는 board 배열과, 모눈종이의 높이와 너비, 사각형의 수를 나타내는 변수도 선언했다.

region 변수는 각 영역의 넓이를 구할때 사용할 변수로, 영역마다 0으로 초기화해주고 사용할 예정이다.

DFS 메서드

DFS 메서드는 크게 어려운 부분은 없다. 그냥 범위에 안맞거나, 이미 공간을 차지한 곳이라면 리턴한다.

둘 다 해당사항이 아닌경우 해당 지역을 방문했다는 표시로 1의 flag를 해 준 후, 현재 탐색중인 영역의 넓이를 나타내는 region 변수에 1을 더해주고 dfs 탐색을 상하좌우로 실시한다.

메인함수 - 1

처음에 높이, 너비, 사각형의 수를 입력받는다.

그리고나서 사각형의 좌표를 입력받고, 위에서 설명한대로 모눈종이에 사각형을 그린다.

이 경우, 예시에 나온 그림과는 상하 반전이 된 형태긴 하지만, 연결요소의 개수를 구하는데에는 문제가 없다.

 

메인함수 - 2

모눈종이를 둘러보며, 0인 곳을 찾아서 dfs를 실시한다. 이 때 region 변수를 0으로 초기화해서 dfs를 돌 때마다 해당 영역의 넓이를 구할 수 있도록 해준다. 그리고나서 result 벡터에 해당 영역의 넓이를 넣어준다.

그리고 결과 벡터를 오름차순으로 정렬한 후에

벡터의 개수가 연결요소의 개수이므로 먼저 출력하고 각 영역의 넓이를 출력해주면 된다.

 

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.