[Algorithm]Baekjoon 12851번 : 숨바꼭질2

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

12851번: 숨바꼭질 2

struct Node
{
    int pos;
    int count;
 
    Node() {};
    Node(int _pos, int _count) : pos(_pos), count(_count) {};
};
 
bool visit[100001] = { false };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int startPos, destPos;
    int minDepth = -1000;
    int minCount = 1;
 
    cin >> startPos >> destPos;
 
    queue<Node> q;
    q.push(Node(startPos, 0));
    visit[startPos] = true;
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curPos = curNode.pos;
        int curCount = curNode.count;
        visit[curPos] = true;
 
        if (curCount == minDepth + 1) break;
        if (minDepth == curCount && curPos == destPos) ++minCount;
        if (curPos == destPos) minDepth = curCount;
 
        if (curPos * 2 <= 100000 && !visit[curPos * 2])
        {
            q.push(Node(curPos * 2, curCount + 1));
        }
 
        if (curPos + 1 <= 100000 && !visit[curPos + 1])
        {
            q.push(Node(curPos + 1, curCount + 1));
        }
 
        if (curPos - 1 >= 0 && !visit[curPos - 1])
        {
            q.push(Node(curPos - 1, curCount + 1));
        }
    }
 
    cout << minDepth << endl << minCount;
 
    return 0;
}

예전에 풀었던 숨바꼭질문제의 응용문제다. 4인가까지 있는거같다. 전부 풀어볼예정이다.

숨바꼭질1의 문제같은 경우는 최솟값만 구하면 끝나는 문제였다.

하지만 이번문제인 숨바꼭질2는 최솟값과, 최솟값 개수를 구하는 문제이다.

 

단순히 최솟값만 구하는 문제였다면, 큐에서 꺼낸 노드의 위치값과 목표위치값이 같은 순간의 count값, 즉 트리의 깊이값이 최솟값이기 때문에 바로 반복문을 탈출하고 (이미 최솟값을 구했기 때문에 더이상 진행할 필요가 없다) 값을 출력하면 된다. 물론 반복문을 탈출 안하더라도 큐는 결국 알아서 비워지긴 하는데 불필요한 행위이므로 괜히 시간만 더걸린다.

그래서 애초에 최솟값만 구하는 문제는, 큐에 넣을때 바로 방문체크를 해버린다.

자 이게 뭘 의미하냐가 중요하다. 

 

목표노드가 뎁스3에 있다고 가정하자. 목표지점뎁스가 3이라 가정하면 부모는 2일 것이다.
뎁스2에서 뎁스3인 자식노드를 조건에 맞게 만드는 단계에서 방문 안한것만 만들어서 큐에 푸쉬 후 '바로' 방문체크를 해버리기 때문에, 나머지 뎁스2의 노드들은 이미 이전의 뎁스2노드들에서 방문체크를 했던 자식노드를 아예 못만든다.
즉, 목표지점의 노드가 뎁스3에 있을 경우, 이 목표노드는 뎁스3에 딱 한개만 있다.
애초에 하나의 값에대해서 딱 한개만 만들고 같은 뎁스안의 노드들이 같은값으로 자식노드를 못만들게 막아버렸기 때문이다.  

최솟값만 구해도 되는 문제는 이렇게 하는게 제일 효율적인게 맞다.
불필요한 노드를 만들어서 큐에 넣을필요가 전혀 없으니까. 그래서 일치하는값 찾는순간 반복문을 탈출해도되는것이다.

 

 

하지만 숨바꼭질2번문제같은 경우,최솟값의 개수도 구해야한다.
즉 첫 목표노드를 찾은 이후, 해당 노드가 있는 뎁스에 같은값의 노드가 몇개있는지 찾아야한다.
이미 말했다시피 기존처럼 큐에넣을때 방문체크를 해버리면 목표노드가 그 뎁스에 1개밖에 없기 때문에 하면 안된다. 

대신 큐에서 꺼낼 때 방문체크를 하면된다. 꺼낼때 하기때문에 이미 꺼낸노드의 뎁스에 한해서는 다른 목표노드가 존재할 수도 있다. 대신 중복된값에 대해 자식노드를 더이상 안만들뿐이다.
그러면 뎁스2에서는 뎁스3에 대한 자식노드를 전부 큐에 넣을 수 있다.
그리고 처음 조건에 맞는 뎁스가 최소값이기 때문에, 처음 조건에 맞을때 값을 저장해놓고 큐에서 노드를 꺼낼때마다 해당노드의 뎁스가 최소값이면서 목표위치값이 맞을때마다 카운팅을 해주면 된다.

그리고 이후에 노드를 꺼냈는데 최솟값+1인 노드가 나온다면 바로 반복문을 탈출해주면 된다.

탈출을 안하더라도 결국 큐는 비워지겠지만 이미 뎁스가 최솟값인 노드는 전부 카운팅했기 때문에 이후의 작업은 무의미하다. 위 문제같은 경우, 저 반복문탈출코드가 있는 코드는 12ms가 나왔고 없는코드는 24ms가 나왔다.