[백준 13549][C++] 알파벳

문제 링크

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

13549번: 숨바꼭질 3

오늘의 생각 : 0 - 1 bfs를 배웠다.

---

◆문제 해결 및 설명◆

문제 해설 : 0초가 걸리는 *2 순간이동과 1초가 걸리는 좌우1칸 이동을 통해 가장 빠르게 목적지(동생)에게 도착하자.

 

최단거리 문제중 가중치가 0또는 1이므로 다익스트라를 통해 풀 수 있겠다는 것을 알았지만, 최근 배운 0 - 1 bfs를 사용해 풀어보았다.

0 - 1 bfs는 다익스트라에서 쓰는 queue를 priority_queue처럼 정렬 관계를 가지게 함으로써 가장 거리가 짧은 친구부터 계산을 먼저하는 방식이다. 하지만 queue는 앞에 삽입이 어렵기 때문에, 코드를 통해 순서에 맞게 push_front와 push_back을 해서 이를 해결하는 방식이다. (입력만으로 우선순위를 맞출 수 있어 가중치가 0또는 1일 때만 사용이 가능하다.)

 

distanceArr은 시작 위치에서 갈 수 있는 최선의 시간을 저장한다.

visited를 통해 방문여부를 확인하여 중복 연산을 방지한다.

시작 위치를 queue에 넣어주고 방문여부를 확인, 이후 순간이동(가중치 0)을 queue의 앞에 추가하고 좌우1칸 이동(가중치 1)은 뒤에 추가함으로 우선순위를 지켜준다.

vector<int> distanceArr;
vector<int> visitied(INF);
void bfs01(int now, int goal, int time)
{
    distanceArr[now] = 0;
    deque<pair<int, int>> dq;
    dq.push_front({now, time});

    while (!dq.empty())
    {
        int position = dq.front().first;
        int seconds = dq.front().second;
        dq.pop_front();

        if (visitied[position] == 1)
        {
            continue;
        }
        visitied[position] = 1;

        if (position * 2 < INF && seconds < distanceArr[position * 2])
        {
            distanceArr[position * 2] = seconds;
            dq.push_front({position * 2, seconds});
        }
        if (position + 1 < INF && seconds + 1 < distanceArr[position + 1])
        {
            distanceArr[position + 1] = seconds + 1;
            dq.push_back({position + 1, seconds + 1});
        }
        if (-1 < position - 1 && seconds + 1 < distanceArr[position - 1])
        {
            distanceArr[position - 1] = seconds + 1;
            dq.push_back({position - 1, seconds + 1});
        }
    }
}

 

◆코드 전문◆

#include <iostream>
#include <queue>

using namespace std;

int now, goal, INF = 1e6 + 10;
vector<int> distanceArr;
vector<int> visitied(INF);

void bfs01(int now, int goal, int time);

int main()
{
    cin >> now >> goal;
    distanceArr = vector<int>(INF, 1e8);
    if (now == goal)
    {
        cout << 0;
        return 0;
    }
    bfs01(now, goal, 0);
    cout << distanceArr[goal];
}

void bfs01(int now, int goal, int time)
{
    distanceArr[now] = 0;
    deque<pair<int, int>> dq;
    dq.push_front({now, time});

    while (!dq.empty())
    {
        int position = dq.front().first;
        int seconds = dq.front().second;
        dq.pop_front();

        if (visitied[position] == 1)
        {
            continue;
        }
        visitied[position] = 1;

        if (position * 2 < INF && seconds < distanceArr[position * 2])
        {
            distanceArr[position * 2] = seconds;
            dq.push_front({position * 2, seconds});
        }
        if (position + 1 < INF && seconds + 1 < distanceArr[position + 1])
        {
            distanceArr[position + 1] = seconds + 1;
            dq.push_back({position + 1, seconds + 1});
        }
        if (-1 < position - 1 && seconds + 1 < distanceArr[position - 1])
        {
            distanceArr[position - 1] = seconds + 1;
            dq.push_back({position - 1, seconds + 1});
        }
    }
}