백준 2583 영역 구하기

1. 좌표값으로 주어진 직사각형들을 배열에다가 표시하기

* 좌표값은 왼쪽 아래(0,0)에서부터 시작하지만 배열은 왼쪽 위부터 (0,0)이 시작한다. 

내가 코드를 짜기 쉽게 처음에는 복잡한 방식으로 접근했다.

위아래 반전시켜서 좌표값이 왼쪽위부터 시작할 수 있도록 하기 위해 가로, 세로 길이를 구하고 반전시켰다.

시작점만 있으면 가로, 세로를 알 수 있기 때문에 시작점을

pair<int,int> start = {m -(y1+h), x1}; // m은 배열의 세로 길이, h는 직사각형의 세로

이렇게 잡아서 직사각형을 색칠했다.

=> 하지만 정확한 좌표값 등을 원하지 않기 대문에 이렇게까지 할 필요가 없었다.

어차피 y값만 달라지지 커넥티드 컴포넌트의 영역과 개수, 그리고 사이즈는 달라지지 않는다.

*기억해야할 것: 좌표값 -> 배열을 위해서는 이상 미만으로 해야함

 

2. 커넥티드 컴포넌트의 사이즈 구하기

이는 void를 리턴하는 dfs와 달리 int를 리턴한다. 탐색을 하며 자식의 개수 + 1 (본인노드)를 리턴하는 식이다.

가중치가 모두 1인 그래프의 커넥티드 컴포넌트의 사이즈 구하기 - (int를 리턴하는 dfs)

** gist의 embed 공유 옵션이 없다. 오잉?