[백준] 산책 (small)

오랜만에 문제를 풀어봤고 아예 그래프 관련 문제를 다 풀어보고 싶은 욕심에 하나씩 다 해보기로 했다. 이번 문제는 내가 너무 복잡하게만 생각안했다면 훨씬 간단 했겠지만 아쉽게도 복잡하게 생각하는 바람에 문제 자체가 훨씬 어렵게 풀었다.

마지막 줄에 산책을 시작하는 지점과 끝나는 지점을 주는데 도착지점까지에 최소 거리인 루트를 구하고 또 돌아오는 장소에 최소 거리 루트도 구해서 합한 거리를 출력하면 됐었다.

되게 까다롭다고 생각했던 조건 중 하나는 여러 가지의 짧은 거리의 경로가 존재 한다 했을때, 1 4 3 2 와 1 3 4 2 중 사전순으로 먼저오는 1 3 4 2 를 선택 했어야했다.

문제에서 나온 사전순으로 먼저 오는 루트라는 설정때문에 고민을 많이 했지만 BFS의 특징만 잘 이해하면 간단한거를 복잡하게 생각했던것이다. 어느 루트가 최소 거리이든 간에 사실상 BFS를 사용하고 마지막 루트로 도작하게 된다면 그것 자체가 최소 거리 이기때문에 내가 해야 하는건 그래프 설정을 한 후에 순서를 사전순으로만 바꾸면 어쨌든 도착하는 장소는 최소 루트의 사전순으로 먼저오는 경로가 될수밖에 없던것이었다!

메인 솔루션이었고 귀찮아서 Input() 을 제거하고 솔루션 부분에서 모든 인풋을 넣어주었다.

마지막으로는 BFS 코드가 있고 그래프에 BFS를 탐색하는 가장 교과서 적인 방법으로 코드를 작성했다. 사실 curr_path 라는 변수도 필요없이 거리만 넣었어도 성공 했을거지만 경로를 알고싶었어서 넣었던 코드였다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, M;
pair<int,int> startEnd = {-1,-1}; 


struct Info{
    int nodeNum, dist; 
    vector<int> path; 
};

vector<Info> bfs(vector<vector<int>>& adj, vector<bool>& visited,int start, int end){
    queue<Info> q;
    Info startNode;
    startNode.nodeNum = start; 
    startNode.dist = 0; 
    q.push(startNode); 
    vector<Info> container; 
    int curr_min = INT_MAX; 
    visited[start] = true; 
    while(!q.empty()){
        int size = q.size(); 
        for(int i = 0; i < size; i++){
            Info first = q.front(); 
            q.pop(); 
            int curr_node = first.nodeNum; 
            int curr_dist = first.dist; 
            vector<int> curr_path = first.path; 
            curr_path.push_back(curr_node); 

            if(curr_node == end){
                first.path = curr_path; 
                container.push_back(first);
                return container; 
            }

            for(int nodes : adj[first.nodeNum]){
                if(!visited[nodes]){
                    if(nodes != end) visited[nodes] = true; 
                    q.push({nodes,curr_dist+1,curr_path}); 
                }
            }
        }
    }


    return container; 

}

void Solution(){
    cin >> N >> M; 
    vector<vector<int>> adj(N+1); 
    vector<bool> visited(N+1,false); 

    for(int i = 0; i < M; i++){
        int node1, node2;
        cin >> node1 >> node2; 
        adj[node1].push_back(node2); 
        adj[node2].push_back(node1); 
    }

    for(int i = 1; i <= N; i++) sort(adj[i].begin(),adj[i].end()); 

    int start, end; 
    cin >> start >> end; 
    startEnd.first = start, startEnd.second = end; 

    vector<Info> first = bfs(adj,visited,startEnd.first,startEnd.second); 
    for(int i = 1; i <= N; i++) visited[i] = false; 
    for(int& n : first[0].path){
        if(n == startEnd.first || n == startEnd.second){
            continue; 
        }
        visited[n] = true; 
    }
    vector<Info> second = bfs(adj,visited,startEnd.second,startEnd.first); 

    cout << first[0].dist + second[0].dist; 

}


void Solve(){
    //Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:

1. 너무 복잡하게 생각하지말자
2. BFS의 특징을 잘 이해하자.