[BOJ] 백준 1697 숨바꼭질

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

1697번: 숨바꼭질

해결사항:

수빈이는 현재 위치에서 3가지로 이동할 수 있다.

위 3가지 이동을 하나의 그래프의 신장으로 보았을때 그래프를 신장해가며 너비 우선 탐색을 진행하다보면 동생의 위치를 알 수 있다.

문제를 해결하면서 첫번째에 봉착한 문제는 "몇 초"가 걸리는지를 함께 아는것이 중요하다.

 

제시된 예제 입력을 통해 알아보자.

---

예제 입력: 5 17

예제 출력: 4

---

가장 먼저 든 생각은 트리를 만드는 것이었다.

트리를 만들고, 트리를 신장해 나가며 해당 target 숫자를 찾는다면, 찾은 순간의 트리의 level에서 1을 빼면

수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 나오게 된다.

그림을 통해 알아보자.

수빈이가 처음 움직일 수 있는 위치

이처럼, 처음 위치가 5일 경우에는 4, 6, 10으로 움직일 수 있다.

수빈이가 4로 움직였다면 움직일 수 있는 위치

수빈이가 4로 움직였으면, 다시 3, 5, 8로 움직일 수 있다.

하지만 한쪽 방향으로만 계속 내려갈 경우가장 빠른 시간을 구할 수 없기 때문에

트리를 신장하면서 동시에 BFS를 이용하여 순회를 하며 찾는것이 적절하다!

 

하지만 무작정 위 방법만을 사용하여 순회를 하게 된다면, 아마 메모리 부족의 문제에 봉착할 것이다.

위 방법만으로 한계 없이 트리를 신장하게되면, 여러가지 문제점들이 생겨나게 되고, 아래 3가지 조건을 만족하게되면 메모리 부족 문제를 해결할 수 있다.

1.  중복된 위치 신장
   이는 아래 그림으로 한번에 표현이 가능하다.
   

   

   중복되는 경우

   위 그림과 같은 경우, 이미 5를 한번 신장하여 순회를 진행하였지만,
   트리의 자식 노드들 중에서 같은 숫자(위치)가 한번 더 나오게 되어 중복해서 신장을 하게되면
   메모리를 낭비하게 된다.
   
   따라서, visited와 같은 변수를 통해 해당 숫자가 신장되었는지 를 확인한다
   여기서 visited는 해당 노드를 방문했는지를 나타내는것이 아니기 때문에 기존에 알려진 BFS와는 조금 다르게 사용된다.
   
   
2. 위치가 0보다 작아진 경우
   

   

   위치가 0보다 작을 경우

   여기서 수빈이가 위치를 1에서 시작하여 동생을 찾아 나섰다고 해보자.
   만약에 동생을 찾기위해서 3초 이상의 시간이 걸린다고 하였을때, 위 그림과 같은 문제가 발생할 수 있다.
   한번 위치가 음수로 내려가기 시작하면, 절대 동생을 찾을수 없는 위치로 트리가 신장하게 된다.
   위 그림에서 -1로 처음 위치가 음수로 내려갔을 때, 신장할 수 있는 위치는 -2, 0, -2로 신장하게 되는데
   첫번째 규칙에 따라 0은 이미 방문하여 신장하지 않지만, -2는 이제 다시는 양으로 돌아오지 않는다. 혹은 돌아온다고 해도 오랜 시간이 지난 후에 돌아오게 될 것이고, 이는 메모리 부족을 불러온다.
   
   
3. 위치가 최대치를 초과한 경우
   위 문제에서 동생은 0 부터 100,000 사이에 위치한다. 만약에 수빈이가 동생을 찾다가 최대치를 초과했다고 해보자.
   

   

   최대치를 초과한 경우

   만일 이 경우에서 100002로의 신장을 인정한다고 하자.
   동생의 위치를 100000이라고 할때, 과연 100002를 지나가는것이 가장 빠를까?
   아마 아닐것이다. 50000을 통해 100000으로 가면 2초 더 빠르고, 혹은 현재 이 노드까지 오기도 전에 끝났을수도 있다.
   결국 최대값을 초과하는 위치에서 커지는 방향은 더이상 무의미하고, 남은 방향은 1씩 작아지는 것 밖에 없고, 1씩 작아지며 동생을 찾는것보다 더 빠르게 탐색이 끝났을 것이다.
   
   

위 3가지 조건들을 이용하여 코드를 작성했다.

먼저 방문한 노드들을 기록하기 위해 map을 사용했다.

map<int, bool> m_table;
map<int, bool>::iterator p;

그리고 각 노드를 저장할 노드를 만들었다.

level은 트리의 level을 의미하고, location은 현재 위치(숫자)를 나타낸다.

walk_b와 walk_f는 각각 back인 -1, front인 +1만큼 움직이는 노드를 가리키고

teleport는 x2만큼 움직이는 노드를 가리킨다.

typedef struct Node{
    int level = 1;
    int location;
    Node* walk_b = nullptr;
    Node* walk_f = nullptr;
    Node* teleport = nullptr;
}Node;

walk_back함수이다.

현재 위치한 노드에서 -1만큼 신장할 수 있는지를 알아본다.

신장 조건은 현재노드의 위치 - 1 은 0보다 커야하고 (조건 2, node->location -1 >= 0)

중복되지 않아야 한다(조건 1, p == m_table.end())

Node* walk_back(Node* node){
    p = m_table.find(node->location - 1);
    if(node->location-1 >=0 && p == m_table.end()){

        Node* new_Node = new Node;
        new_Node->level = node->level + 1;
        new_Node->location = node->location - 1;

        m_table[new_Node->location] = true;

        return new_Node;
    }

    return nullptr;
    
}

walk_front와 teleport는 서로 위치가 늘어나는 방향으로 신장하기 때문에, 동일한 조건으로 신장 여부를 확인했다.

신장 조건은 현재노드의 위치 + 1 / 현재노드의 위치 x 2 는 100000보다 작아야하고 
(조건 3, node->location +1 <= 100000 / node->location * 2 <= 100000)

중복되지 않아야 한다(조건 1, p == m_table.end())

Node* walk_front(Node* node){
    p = m_table.find(node->location + 1);
    if(node->location+1<=1000001 && p == m_table.end()){

        Node* new_Node = new Node;
        new_Node->level = node->level + 1;
        new_Node->location = node->location + 1;

        m_table[new_Node->location] = true;
        
        return new_Node;
    }

    return nullptr;
}

Node* teleport(Node* node){
    p = m_table.find(node->location * 2);
    if(node->location*2<=1000001 && p == m_table.end()){

        Node* new_Node = new Node;
        new_Node->level = node->level + 1;
        new_Node->location = node->location * 2;

        m_table[new_Node->location] = true;
        
        return new_Node;
    }

    return nullptr;
}

위 조건들을 이용하여 신장이 가능하다면 기존의 node보다 level을 1 더 크게 설정하고, location은 기존 조건에 맞게 설정해주고, m_table[new_Node->location]=true를 이용하여 방문을 표시한다.

 

---

int find_fastest_time(int start, int target){
    queue<Node*> que;
    
    Node* root = new Node;
    root->location = start;
    m_table[start]=true;
    que.push(root);

    while(true){
        Node* temp = que.front();
        que.pop();
        if (temp != nullptr){
            if((temp->location) == target){
                return temp->level-1;
            }

            temp->walk_b = walk_back(temp);
            que.push(temp->walk_b);
            temp->walk_f = walk_front(temp);
            que.push(temp->walk_f);
            temp->teleport = teleport(temp);
            que.push(temp->teleport);

        }
    }
}

BFS지만 while(true)로 한 이유는 트리의 신장과 탐색이 끝날때 까지 루프를 돌 것이고, 결국 큐는 비워질 일이 없는것 같아 while 의 조건을 항상 도는것으로 하였다.

위에서 제공된 3가지 함수들은 트리 신장을 하지 못할 경우 null-pointer를 반환하므로, 조건문에서 null-pointer인지 아닌지 확인을 하고, location이 target과 동일하다면 그 노드의 level에서 1만큼 뺀 값을 반환하는 함수이다.

순서는 신장->큐에 삽입 순서로 진행된다.

 

 

Icons made by Smashicons from www.flaticon.com