[Algorithm]Baekjoon 1987번 : 숨바꼭질

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
 
using namespace std;
 
 
// 목표
    
struct Node
{
    int num;
    int count;
 
    Node(int _num, int _count) : num(_num), count(_count) {};
};
 
 
int solution(int n, int m)
{
    int answer = 0;
    bool visit[100001] = { false };
 
    queue<Node> q;
    q.push(Node(n, 0));
    visit[n] = true;
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curNum = curNode.num;
        int curCount = curNode.count;
 
        if (curNum == m)
        {
            answer = curCount;
            break;
        }
 
        if (curNum+1 >= 0 && curNum+1 <= 100000 && !visit[curNum + 1])
        {
            visit[curNum + 1] = true;
            q.push(Node(curNum + 1, curCount + 1));
        }
        if (curNum - 1 >= 0 && curNum - 1 <= 100000 && !visit[curNum - 1])
        {
            visit[curNum - 1] = true;
            q.push(Node(curNum - 1, curCount + 1));
        }
        if (curNum * 2 >= 0 && curNum * 2 <= 100000 && !visit[curNum * 2])
        {
            visit[curNum * 2] = true;
            q.push(Node(curNum * 2, curCount + 1));
        }
    }
 
    return answer;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n = 0;
    int m = 0;
 
    cin >> n >> m;
 
    int result = solution(n, m);
 
    cout << result << endl;
}

 

DFS로 하려다가 생각대로 안풀려서 BFS로 했더니 거의 바로 풀렸다. BFS문제는 그래도 꽤 풀었다보니 코드가 금방 연상이된다. 주의해야할것은 이미 만들었던 숫자에대해선 방문체크를 함으로써 무한반복을 피해야한다.

그다음은 그냥 조건에 따라 +1,-1,*2 노드를 넣으면 된다. 

조건문을 체크할 때 주의할 점은, 위의 코드를 보면 알겠지만 if문에 curNum -1 >= 0 같이 숫자가 정상범위안에있는지 먼저 체크하고 방문체크를 해야한다. 당연히 배열의 정상인덱스를 접근해야하니까 그런거긴 한데, 저 순서가 틀리면 안된다는 거다. if문은 왼쪽조건부터 먼저 검사한다는게 중요하다.