(백준 2644번 촌수계산 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 1

오늘부터는 bfs를 풀어볼까 한다! 역시나 오늘도 reference는 라이님의 블로그!

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220785747864&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

너비 우선 탐색(Breadth-First Search) (수정 2018-11-22)

 

백준 2644번

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

2644번: 촌수계산

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
public:
    int N;
    vector<vector<int>> adj;
    vector<bool> visited; // bool로 변경

    Graph(int N) : N(N), adj(N+1), visited(N+1, false) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int bfs(int start, int end) {
        queue<int> q;
        q.push(start);
        visited[start] = true; // 시작점 방문 처리

        int level = 0;
        while (!q.empty()) {
            int qsize = q.size();
            for (int i = 0; i < qsize; i++) {
                int curr = q.front();
                q.pop();

                if (curr == end) return level; // 종료 조건 검사

                for (int next : adj[curr]) {
                    if (!visited[next]) {
                        visited[next] = true;
                        q.push(next);
                    }
                }
            }
            level++;
        }
        return -1; // 경로가 없는 경우
    }
};

int main() {
    int n; cin >> n;
    int start, end; cin >> start >> end;
    int m; cin >> m;
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g.addEdge(u, v);
    }

    cout << g.bfs(start, end);
    return 0; 
}

gpt에게 코드를 한 번 더 수정해달라고 한 결과다. Graph 초기화 방법이 조금 더 심플해졋따!!