백준 1697. 숨바꼭질 [실패]

1.실패 원인

저번 포스팅과 마찬가지로 해당 문제를 그래프 문제로 인식하지 못했다. 다시 문제를 살펴보니 하나의 경우를 선택했을 때 여러 경우를 다시 선택할 수 있다는 점에서 그래프 문제로 인식해야 했고, 최소 경로를 찾는 문제와 동일하기 때문에 BFS를 선택하여 푸는 문제라는 것을 알아체야 하는 문제이다.

2.작성 코드

#include <iostream>

#include <queue>

using namespace std;

 

const int MAX = 100000 + 1;

bool visited[MAX];

 

int minSecond(int N, int K)

{

        queue<pair<int, int>> q;

 

        q.push(make_pair(N, 0));

        visited[N] = true;

 

        while (!q.empty())

        {

                 int curLoc = q.front().first;

                 int curSec = q.front().second;

                 q.pop();

 

                 if (curLoc == K) //목적지 도달 시 break

                         return curSec;

 

                 //세 가지 경우의 수

                 //이미 방문한 지점은 큐에 넣지 않는다

                 if (curLoc + 1 < MAX && !visited[curLoc + 1])

                 {

                         q.push(make_pair(curLoc + 1, curSec + 1));

                         visited[curLoc + 1] = true;

                 }

                 if (curLoc - 1 >= 0 && !visited[curLoc - 1])

                 {

                         q.push(make_pair(curLoc - 1, curSec + 1));

                         visited[curLoc - 1] = true;

                 }

                 if (curLoc * 2 < MAX && !visited[curLoc * 2])

                 {

                         q.push(make_pair(curLoc * 2, curSec + 1));

                         visited[curLoc * 2] = true;

                 }

        }

}

 

int main(void)

{

        int N, K;

        cin >> N >> K;

 

        cout << minSecond(N, K) << "\n";

 

        return 0;

}



// 출처: https://jaimemin.tistory.com/581 [꾸준함]

3.참고 코드

https://jaimemin.tistory.com/581

백준 1697번 숨바꼭질

4. 해결 방안

BFS, DFS를 언제 사용해야 하는지에 대해서 키워드 하나가 더 늘어난 느낌이다. 꼭 2차원 배열을 주거나 노드 경로의 언급 없이도 특정 숫자에서 시작해서 특정 숫자로 도착해야 한다면 그래프 문제임을 인식해야 한다. 

 

https://sanghun219.tistory.com/130?category=894931

제목 백준 2146. 다리 만들기 [실패]

이전 그래프 문제에서 BFS,DFS를 언제 사용해야하는지 작성하였다. 

연결 요소 - DFS

최단 거리 - BFS 임을 기억하자