백준 26009. 험난한 등굣길

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

26009번: 험난한 등굣길

 

문제의 핵심은 교통 정체가 일어나는 부분을 지도에 표시하는 것이다.

만약 그냥 [r,c]로 부터 d 거리 이내의 좌표를 단순히 모두 탐색하여 표시하면 정체구역의수가 최대 3000개, 거리 d가 최대 3000이기 때문에 시간초과가 날 것이다.

 

생각해보면 어처피 교통정체 구간으로는 이동을 하지 못하기 때문에 [r,c]에서 d 이내의 좌표를 모두 표시할 필요는 없고 [r,c] 에서 정확히 d 만큼 떨어진 교통정체의 외곽 부분만 표시해도 된다.

 

[r,c]에서 d 거리 떨어진 곳을 그림으로 그려보면 다이아 몬드 형태가 되는 것을 알 수 있다.

예를들어 (r,c) 에서 2 만큼 떨어진 구역을 1로 표시하면 아래와 같게 된다.

		1
	1		1
1		(r,c)		1
	1		1
		1