14474번 : 尾根 (Ridge)

https://www.acmicpc.net/problem/14474

 

H, W 크기의 그래프가 있다. 이는 해당 부분의 높이를 의미하며 물은 높이가 높은곳에서 낮은곳으로 흐른다. 어떤 구역에 비가 내렸을 때, 최종적으로 비가 고이는 곳이 2개이상인 지역의 개수를 구하라.

 

3 5
5 3 8 2 14
9 10 4 1 13
12 7 11 6 15

예제 2번의 오른쪽아래 15, 13 부분을 보면 각 부분에서 비가 내렸을 때 1로 비가 고이지만 비가 고이는곳이 한 곳이기 때문에 해당하지 않는다. 12의 경우에는 7, 3에서 비가 고인다.

 

순서대로 접근해보자

1. 우선 비가 고이는 장소의 특징은 상하좌우가 자신보다 높은 곳이다. 한 곳이라도 자신보다 낮은 곳이 있을 경우 그 부분으로 흘러가기 때문이다. 이를 전체 탐색을 하자.

2. 처음에 접근법은 각 위치에서 비를 흘려준다고 생각했는데 그럼 최악의 케이스 S자로 꼬여 한곳에서만 비고 고인다 생각했을 때, (1000*1000)^2 만큼 시간이 든다.

3. 반대로 접근해야한다. 결국 비가 고이는 곳으로 오기 때문에 비가 고이는 곳에서 시작해서 흘러보내는 지점에 길을 추가해주고 나중에 정산하면 된다.

 

그림으로 보면 이런느낌이고 하나이상의 도착지인 곳의 개수를 고르면된다.