백준 18513 <샘터>

치킨 집의 위치에서부터 BFS를 하는 문제! 생각보다 어렵지는 않았지만.. 그놈의 실수.. 실수.. ㅠ

접근 방법만 알게된다면 쉽게 풀 수 있는 문제였다.

 

문제를 먼저 이해하자고 하면 치킨집에서 가까운 순서대로 집을 놓고 개수를 구하는 것이다.

즉 가까운 곳부터 집을 놓는다 --> 너비 탐색 이렇게 되는 것이다.

 

이 문제에서 주요하게 생각해야 하는 점은 범위!! 

 

총 거리의 합이 int형이 아니고 long 형의 범위가 된다는 것을 주의해야 한다!

 

이것 이외에도.. 메모리... 초과를 주의하자.. 이놈의 습관 때문에 방문처리를 해주는 visit함수를 boolean 형이 아닌 int 형으로 사용한다면... 메모리 펑... 펑... 초과를 하게 된다.

 

위에 num을 저렇게 크게 잡아준 이유는 음수에도 위치가 놓일 수 있기 때문에 음수가 가질 수 있는 범위만큼 양수로 옮겨 주기 위해서이다.

이 이후에 치킨집의 위치를 Point형식으로 x좌표는 현재 위치 y 좌표는 치킨집에서의 거리를 queue에 넣어준다.

치킨집 위치에서는 물론 치킨 지수가 0이기 때문에  <치킨집 위치, 0>을 큐에 넣어준다

 

 

 

다음은 그지점을 시작으로 BFS를 실시한다.

 

이렇게 방문처리를 int형으로 하면 메모리가 터진다.. boolean형의 소중함을 깨닫는 문제였다..