[C++] 백준 22868번: 산책 (small)

🔗 문제

22868번: 산책 (small)

22868번: 산책 (small)

 

🖍 풀이

 

다익스트라를 이용해서 최소 길이를 찾으려고 했다.

 

하지만 문제를 읽어보면 모든 간선간의 이동 비용은 1이므로 단순하게 BFS로 풀면 된다.

위 조건 덕분에 정렬 후에 가장 처음 만난 노드로 이동하는 것이 최소 비용이 된다. 

 

1. S → E까지의 최소 이동 비용을 구한다.
2. E → S 까지 최소 이동 비용을 구한다.

1 + 2 의 비용 합산 비용으로 정답을 찾을 수 있다.

 

 

 

BFS(S, E);

// BFS를 2번 돌리기 위해 재방문 확인 배열을 초기화 시켜준다. 
memset(visited, false, sizeof(visited));

// S -> E 까지 간 경로를 또 방문하지 않기 위한 작업
int v = route[E];
while(v != 0)
{
    visited[v] = true;
    v = route[v];
}

BFS(E, S);

---

주의할 점

 

BFS를 돌리기 전에 각 정점이 갈 수 있는 노드를 정렬해준다.

 

정점 S에서 정점 E로 이동할 때, 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

 

graph[x]와 연결된 노드를 저장해주었는데 정렬을 하면 사전순으로 선택할 수 있게 된다. 

// 우선 순위를 위해 정렬
for(int i=1; i<=N; ++i)
  std::sort(graph[i].begin(), graph[i].end());

 

노드 번호는 1부터 시작한다는 점을 유의하자..!

나는 정렬 범위를 잘못 줘서 틀렸습니다를 봤다😭

 

💾  소스

#include <iostream>
#include <queue>
#include <memory.h>
#include <vector>
#include <algorithm>

const int MAX = 10010;
int N, M, S, E, answer = 0;

bool visited[MAX] = {false, }; // 재방문 확인 배열
int route[MAX] = {0, }; // route[x]는 x 노드에 방문하기 전의 노드 값을 가진다.

std::vector<int> graph[MAX];

void BFS(int start, int end)
{
    std::queue<std::pair<int, int>> q;
    
    q.push({start, 0});
    visited[start] = true;
    
    while(!q.empty())
    {
        int edge = q.front().first;
        int cost = q.front().second;
        q.pop();
            
        for(int i=0; i<graph[edge].size(); ++i)
        {
            int next = graph[edge][i];
            
            if(visited[next])
                continue;
            
            visited[next] = true;
            route[next] = edge;
            q.push({next, cost+1});
            
            if(next == end)
            {
                answer += (cost+1);
                return;
            }
        }
    }
    
}

int main()
{
    int A, B;
    
    std::cin >> N >> M;
    
    for(int i=0; i<M; ++i)
    {
        std::cin >> A >> B;
        graph[A].push_back(B);
        graph[B].push_back(A);
    }
    
    // 우선 순위를 위해 정렬
    for(int i=1; i<=N; ++i)
    {
        std::sort(graph[i].begin(), graph[i].end());
    }
    
    std::cin >> S >> E;
    
    BFS(S, E);
    
    memset(visited, false, sizeof(visited));
    int v = route[E];
    while(v != 0)
    {
        visited[v] = true;
        v = route[v];
    }
    
    BFS(E, S);
    
    std::cout << answer;

    return 0;
}