BFS 문제를 어떤것들 풀까 하고 보던중에 발견한 문제이다. 언뜻보기에는 간단한 문제지만, 난 어느부분에서 막혔었고 배운점들도 있었기에 적어본다.
문제 내용은 되게 간단하다. 사각형 밑에 가장자리에 도달하기까지 숫자들을 지나게 될텐데 이 경로상에 절대값중에 마지막 숫자에 도달하기까지 가장 작은값을 리턴하면 되는문제이다.
그냥 BFS로 첫번째 숫자부터 퍼져 나가서 마지막 숫자에 도달할시, (x == heights.size()-1 && y == heights[0].size()-1) 에 있었던 숫자를 리턴하면 되는게 아니였지만 내가 했던 시도는 어이없는 문제로 막혔었다.
여러번의 cout 을 했던 흔적이 보이는데...그렇다 난 이때 바보같이 queue 를 사용했던 실수를 하였다. 어쨌든 문제에서 원하는거는 최소한의 절대값이고 난 이부분을 queue 로 구할려고 했었던것이다.
이게 훨씬 더 깔끔한 값이다. 둘이 똑같은 코드를 썼음에도 두번째 코드가 훨씬 더 빠르고 간단해진거는 priority_queue 를 절대값 기준으로 pop해주고 push 해주니 결국에 마지막에 도달했을때는 가장 적은값이 가있기 때문이다. 여기서 배운점이 있다.
우리가 흔히 BFS 에서는 queue 구조와 priority_queue 구조를 써주고는 하는데.
일반적인 queue 를 사용할때는 기본적인 bfs형식으로 모든 "경우의 수" 를 탐색하고싶을때 쓰인다.
반대로 Priority_queue 같은경우에는 dijkstra 알고리즘 유형의 문제, 그러니깐 최소한의 경로를 찾고싶을때 쓰이는것이다.
다익스트라에는 익숙해진 나이지만 보통은 weighted graph에서만 써봤었기 때문에 생각이 안나고 일반적인 BFS만 떠올랐었기 때문에 이 쉬운문제에서도 좀 헤맸던거같다.
앞으로는 이런 실수하지말고 문제에서 최소한, 혹은 최대의 값을 구하는 Matrix문제가 나올때는 과감하게 Priority_queue 를 써주는 판단 또한 필요할거같다.
배운점:
1. BFS의 활용
2. 일반 queue 와 priority_queue 의 사용방법
