백준 - 숨바꼭질 시리즈

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

1697번: 숨바꼭질

1697. 숨바꼭질

• 특징
  • 2차원 bfs
• 주의할점
  • 문제 조건을 잘 읽어야 함 (n == k 일수도 잇고, n > k 일 수 있다.  처음에 나는 n < k 인 경우만 고려해서 오류가 났음.)
• 코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include<algorithm>
using namespace std;

int n, k;
int vis[300010];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;

    if(n == k) 
    {
        cout << "0";
        return 0;
    }

    int b = max(n, k);
    
    queue<int> q;
    q.push(n);
    fill(vis, vis+300009, -1);
    vis[n] = 0;
 
    int v = 0;

    while(!q.empty())
    {
        int cur = q.front(); q.pop();
         
        for(int nxt: {cur-1, cur+1, cur*2})
        {
            
            if(nxt < 0) continue;
            if(nxt > b * 3) continue;
            if(vis[nxt] != -1) continue;
            vis[nxt] = vis[cur]+1;

            q.push(nxt);
            
            if(nxt == k)
            {
                v = vis[k];
                break;
            }

        }
    }

    cout << v << endl;

}

12851. 숨바꼭질 2

• 특징
  • queue를 이용한 2차원 bfs
• 주의할 점
  • 큐를 이용하여 bfs를 할 때, 보통 nxt를 queue에 넣고 방문처리를 해준다. 
    
    • 예를 들어, 3이라는 위치를 방문하는데 처음엔 2초가 걸린 애가 왔었고, 그 다음 4초 걸린 애가 오면, 4초 걸린 방식은 필요없기 때문
  • 하지만 이 문제에서 방문처리를 큐에 넣을 때 하는 것이 아니라 pop을 한 후에 한다.
    • 예를 들어, 1 4가 입력되어 1 -> 1+1 -> 2 *2 와 1-> 1*2 -> 2*2를 각각으로 count해주어야하는데, 기존의 하던방식으로는 2라는 위치가 방문처리되어 *2로 오는 과정이 스킵되기 때문이다. 
  • 코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

int n, k;
int vis[300010]; // - + *
int v;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;

    int b = max(n, k);
    int cnt = 0;
    queue<pair<int, int>> q;
    q.push(make_pair(n, 0));
    vis[n] = 1;
    while(!q.empty())
    {
        int cur = q.front().first;
        int dist = q.front().second;

        q.pop();
        vis[cur] = 1;

        if(cnt > 0 && dist == v &&  cur == k)
        {
            cnt++;
        }
        if(cur == k && cnt == 0)
        {
            cnt++;
            v = dist;
        }
        
        for(int i = 0; i < 3; i++)
        {
            int nxt = 0;
            if(i == 0) nxt = cur - 1;
            else if(i == 1) nxt = cur + 1;
            else nxt = cur * 2;

            if(nxt < 0) continue;
            if(nxt > b * 3) continue;

            if(vis[nxt] == 0)
            {
                q.push(make_pair(nxt, dist+1));
                
            }
        }
    }

    cout << v << endl;
    cout << cnt;


}

 

13549. 숨바꼭질 3

• 특징
  • deque를 이용한 2차원 bfs
  • or 우선순위 큐를 이용한 2차원 bfs -> 최소힙
• 주의할 점
  • 0초동안 *2만큼 이동할 수 있다는 조건이 있다. 3가지중 *2연산을 먼저 해야한다. 따라서 해당 연산을 할 때에는, deque의 앞쪽으로 다음 위치를 넣어주었다.
  • 1초가 걸리는 -1, +1 이동은, deque의 뒷쪽으로 다음 위치를 넣어주었다. 
• 코드 - deque

#include <iostream>
#include <vector>
#include <deque>
#include <limits.h>
#include<algorithm>

using namespace std;

int n, k;
int vis[300010];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;

    if(n == k) 
    {
        cout << "0"<< endl;
        return 0;
    }

    int b = max(n, k);

    deque<int> dq;
    fill(vis, vis+300009, -1);
    dq.push_back(n);
    vis[n] = 0;

    int v = 0;
    int ans = 0;
    while(!dq.empty())
    {
        int cur = dq.front();
        dq.pop_front();
        for(int nxt: {cur-1, cur+1, cur*2})
        {
            
            if(nxt < 0) continue;
            if(nxt > b * 3) continue;
            if(vis[nxt] != -1) continue;
            if(nxt == cur * 2)
            {
                vis[nxt] = vis[cur];
                dq.push_front(nxt);
            }
            else 
            {
                vis[nxt] = vis[cur]+1;
                dq.push_back(nxt);
            }    
            if(nxt == k && v == 0)
            {
                v = vis[k];
                break;
            }
        }
    }
    cout << v << endl;

}

• 코드 - 우선순위큐

#include <iostream>
#include <queue>
#include <deque>
#include <limits.h>
#include<algorithm>

using namespace std;

int n, k;
int vis[300010];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;

    if(n == k) 
    {
        cout << "0"<< endl;
        return 0;
    }

    int b = max(n, k);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    fill(vis, vis+300009, -1);
    q.push(make_pair(0, n));
    vis[n] = 0;

    int v = 0;
    int ans = 0;
    bool isFind = false;
    while(!q.empty() && !isFind)
    {
        int cur = q.top().second;
        int dist = q.top().first;
        q.pop();
        for(int nxt: {cur-1, cur+1, cur*2})
        {
            
            if(nxt < 0) continue;
            if(nxt > b * 3) continue;
            if(vis[nxt] != -1) continue;
            
            if(nxt == cur * 2)
            {
                vis[nxt] = dist;
                q.push(make_pair(vis[nxt], nxt));
            }
            else 
            {
                vis[nxt] = dist+1;
                q.push(make_pair(vis[nxt], nxt));
            }
        
            if(nxt == k && v == 0)
            {
                v = vis[k];
                isFind = true;
                break;
            }

        }
    }

    cout << v << endl;


}

 

13913. 숨바꼭질 4

• 특징
  • queue를 이용한 2차원 bfs
  • 키를 자기자신, 값을 부모로 설정하는 map을 정의하고, m[nxt] = cur로 저장.
  • 목적지에서 출발점까지 map을 타고 타고감.
• 코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

int n, k;
int vis[300010];
map<int, int> m; //본인, 부모
vector<int> result;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    int b = max(n, k);
    
    queue<int> q;
    q.push(n);
    fill(vis, vis+300009, -1);
    vis[n] = 0;
 
    while(!q.empty())
    {
        int cur = q.front(); q.pop();
         
        for(int nxt: {cur-1, cur+1, cur*2})
        {
            if(nxt < 0) continue;
            if(nxt > b * 3) continue;
            if(vis[nxt] != -1) continue;
            vis[nxt] = vis[cur]+1;
            m[nxt] = cur;
            q.push(nxt);
            
            if(nxt == k)
            {
                v = vis[k];
                break;
            }

        }
    }

    cout << v << endl;

    int cur = k;
    while(cur != n)
    {
        result.push_back(cur);
        cur = m[cur];
    }
    result.push_back(n);
    reverse(result.begin(), result.end());
    
    for(auto x:result) cout << x << ' ';

}