[SWEA - 4112]이상한 피라미드 탐험

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH

SW Expert Academy

전형적인 BFS문제다.

하지만, 이 문제를 어렵게 만드는 것이 있다면 아마

맵을 형성하는 부분일것이다.

 

우선 맵을 그리기 전에 쉽게 그리기 위하여 먼저 나는 규칙성을 찾았다.

첫째로 아래로 내려가면서 제일 왼쪽을 보면

1, 2, 4, 7, 11, 16, 22 .....

이런식으로 진행되는 수열을 확인할수 있다.

이는 공차가 i로 주어지는 경우고

이를 알았다면 vector를 통해 각 줄에 필요한 만큼의 데이터를 담을수 있게된다.

하지만, 이 방법은 이 문제이기 때문에 가능한 방법이라고 생각도 된다.

데이터의 양이 작아서 다행이다.

이런식으로 map을 만들어주면 된다.

 

그리고 나서는 전형적인 BFS다. 하지만 조금 주의할것이 있다면

우리가 일반적으로 온라인저지에서 풀던 BFS는 4방향 즉, 위 아래 오른쪽, 왼쪽을 탐색하게되는데

본문제 같은경우 탐색의 범위가 6방향이다.

 

이점을 주의해서 문제를 풀었고

하나의 벡터 내부에 있는 최대 크기를 넘어가지 않기 위해 벡터 사이즈나 인덱스 정보를 통해 확인해서 탐색을하면되는데

여기서, 한가지 더 추가하고 싶었던것은 탐색하고있는 점과, 탐색을 해야 할 점의 구분이다.

 

탐색을 해야할 점이 만약 현재 탐색하고 있는 지점의 값보다 크게되면 위로 올라가는 탐색은 하지않아도된다. (왼쪽 방향도 마찬가지다.) 그렇기때문에 현재 크기와 탐색하고자하는 목표치의 크기에 따른 선별적 탐색이 필요하다는 말이다.

그러한 점을 고려해서 BFS를 맞춰주면 답을 맞출수있다.