<baekjoon> 2583- 영역 구하기

<풀이>

직사각형이 없는 영역의 넓이를 구하기 위해 우선 직사각형인 부분은 1이라도 값을 부여하였다.

그리고 bfs를 통해 1이 아닌경우, 그리고 방문한적이 없는 경우(v[nr][nc]가 false인경우) 에만 Queue에 넣고 진행을 하였다.

각 영역의 넓이는 bfs함수 내에서 Queue에 한 칸씩 이동(저장)시마다 cnt변수를 +1해주어서 값을 구하였다.

이렇게 해서 bfs함수가 한번 끝나면 직사각형이 아닌 영억의 개수를 하나 구한거다(size변수).

 

이 문제는 직사각형 범위가 어디든 모양과 크기만같으면 좌표 값이 달라도 상관없이 풀 수 있다. 구해지는 범위의 넓이가 순서가 다르지만 문제의 조건중에 오름차순 정렬이 있으므로 상관없다.

 

<코드>