백준 18243번 [Small World Network](C++) -yes6686- 티스토리

백준 문제 풀이: 18243 [Small World Network]

---

문제 링크: https://www.acmicpc.net/problem/18243

문제 설명:

주어진 네트워크가 "Small World Network"인지 판별하는 문제입니다. 네트워크가 다음 조건을 만족하면 "Small World!"라고 출력하고, 그렇지 않으면 "Big World!"를 출력합니다:

• 모든 정점들이 연결되어 있어야 함 (connected).
• 임의의 두 정점 사이의 최단 거리가 6을 초과하지 않아야 함.

그래프는 \(n\)개의 노드와 \(k\)개의 간선으로 이루어져 있습니다. 간선은 무방향 그래프로 주어집니다.

---

문제 해결 코드

// Small World Network 문제 해결 코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring> // memset 사용
using namespace std;

vector<int> graph[101];
bool visited[101];
int distanceArr[101];
int n;

bool bfs(int start) {
    queue<int> q;
    memset(visited, false, sizeof(visited));
    memset(distanceArr, 0, sizeof(distanceArr));

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                distanceArr[neighbor] = distanceArr[current] + 1;

                if (distanceArr[neighbor] > 6) {
                    return false; // 거리가 6을 초과하면 "Big World!"
                }

                q.push(neighbor);
            }
        }
    }

    // 연결 여부 확인
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            return false; // 연결되지 않은 정점이 있으면 "Big World!"
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int k;
    cin >> n >> k;

    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!bfs(i)) {
            cout << "Big World!" << '\n';
            return 0;
        }
    }

    cout << "Small World!" << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘:
  • BFS를 사용하여 모든 정점에 대해 다음 두 가지 조건을 확인합니다:
  • 최단 거리가 6을 초과하는 정점이 없는지 확인합니다.
  • 모든 정점이 연결되어 있는지 확인합니다.
• 구현 세부사항:
  • visited: 방문 여부를 기록하는 배열입니다.
  • distanceArr: BFS를 통해 계산한 시작점에서 각 정점까지의 최단 거리를 기록합니다.
  • 모든 정점에서 BFS를 실행하여 조건을 만족하는지 확인합니다.
• 시간 복잡도 분석:
  • 각 BFS의 시간 복잡도는 \(O(V + E)\)이며, 모든 정점에서 BFS를 수행하므로 \(O(V \cdot (V + E))\)입니다.
  • 최악의 경우 \(E = O(V^2)\)이므로, 시간 복잡도는 \(O(V^3)\)로 간주할 수 있습니다.

---

결과

이 알고리즘은 주어진 네트워크가 Small World Network인지 확인합니다. 예를 들어:

• 입력:

          6 7
          1 2
          2 3
          3 4
          4 5
          5 6
          1 6
          2 5
          

• 출력: Small World!

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!