문제 : https://www.acmicpc.net/problem/1697
깨달은 것
c++에서의 pair의 편리성, BFS는 탐색 방식이라는 것
1. c++에서 pair는 매우 편리하다!
pair라는 구조체가 c++에는 존재한다. 이는 queue나 vector를 사용할 때 연관성이 있는 두 개의 값을 저장하는데에 매우 유용한 것 같다. 사용 형식은 다음과 같다.
**template<class _T1, class _T2> struct std::pair<_T1, _T2>**
Struct holding two objects of arbitrary type.
Template Parameters:
_T1 – Type of first object.
_T2 – Type of second object. <https://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html\>
File: stl_pair.h실제로 각 값들을 찾아 갈 때 단계를 매겼어야 했는데, 그 단계를 잘 표현해 줄 수 있었다.
예를 들어 5에서의 3가지 탐색(*2, +1, -1)을 하면 각 결과, 10, 6, 4는 각각 1단계, 즉 1초 가 지났다고 간주 할 수 있다. 이때 문제는 10에서 3가지 탐색을 하는 것과 6에서 3가지 탐색을 하는 것은 같은 단계로 간주해야하는 것이었다.
나는 처음에는 이를 수학으로 풀어내려고 했다. 하지만 pair라는 것이 있으면 queue에서 pop한 숫자의 단계에서 +1만 하면 된다.
처음의 수학을 통해 계산하려했던 방식
while (tmp < cnt){ times++; tmp = tmp + pow(3, times); } return times;
pair를 사용한 queue
queue<pair<int, int>> q;
생각해보면 구조체를 사용하는 것이 훨씬 쉽다는 것을 알면서도 고집 부렸던거 같다. 수학 관련해서는 나중에 다른 문제로 연습해보자.
2. BFS는 탐색 방법
BFS는 탐색 방법이다. 꼭 노드들에서 주변 노드들을 탐색하려 할때만 사용하는 방식이 아니다. 탐색이 여러 방법이 있으면 여러 방법의 탐색을 다 해보고 다음 단계로 넘어가는 것이다.
돌다리도 두들겨보고 간다.
int search[3] = {2 * curr, curr + 1, curr - 1}; // search method -> *2, +1, -1최종 코드
https://github.com/dagreatjh359/excercises/blob/main/BFS/1697.c%2B%2B참고해볼만 한 문제
BOJ 5014 : https://www.acmicpc.net/problem/5014
최종 코드 : https://github.com/dagreatjh359/excercises/blob/main/BFS/5014.c%2B%2B
