문제

  • 상근이와 친구들의 관계를 그래프로 나타내었을 때, 시작점(상근이)으로부터 최단거리가 2이하인 정점의 개수를 구하시오.
  • 2 <= n <= 500 (n은 정점의 개수), 1<= m <= 10000 (m은 간선의 개수)
  • 시간 제한 1초
  • 문제 링크

접근 과정

1. 그래프

  • 상근이와 친구들의 관계를 양방향 그래프로 설계합니다.(문제에서 a와 b가 친구 관계이면, b와 a도 친구 관계이다.) 그래프의 자료구조는 인접 리스트를 사용합니다.
  • 탐색의 시간 복잡도는 인접 행렬일 때 O(n^2), 인접 리스트일 때 O(n+m)입니다. 시간 복잡도를 줄이기 위해서 인접 리스트로 구현합니다.

2. 탐색

  • 상근이(시작점) 에서 부터 탐색을 시작한다. 시작점에서 부터 각 정점까지의 최단경로를 구해야합니다.
  • 최단거리 알고리즘에는 대표적으로 1) 다익스트라, 2) 벨만포드, 3) 플로이드-와샬 이 있습니다만, 모든 간선의 가중치가 같을 때에는 BFS가 최단거리를 계산해줍니다. 따라서, 탐색 알고리즘으로 BFS를 사용합니다.

3. 시간 복잡도 계산

  • 1) BFS의 목적은 모든 정점을 방문하는 것이고, 2) 그래프를 구현하는 자료구조 인접 리스트를 사용했습니다. 따라서 BFS를 사용하면 모든 정점과 간선을 딱 한 번씩만 방문하게 됩니다. 시간 복잡도: O(n+m)

  • 2 <= n <= 500 (n은 정점의 개수), 1<= m <= 10000 (m은 간선의 개수) 이기 때문에 O(n+m)은 O(10500) 시간 안에 충분히 수행됩니다.

코드

1. C++

#include <iostream>
#include <vector>
#include <queue>

#define max_int 501
using namespace std;

//시간 복잡도: O(n+m)
//공간 복잡도: O(m)
//사용한 알고리즘: BFS
//사용한 자료구조: 인접 리스트

int n, m, a, b, result;

// 벡터를 인접 리스트로 사용합니다.
vector<int> v[max_int];

// 시작 정점으로 부터의 거리 정보를 담을 배열입니다.
int check[max_int];

void bfs(int start){
    check[start] = 1;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int node = q.front();
        q.pop();

        for(int i=0; i<v[node].size(); i++){
            int next = v[node][i];
            if(check[next] == 0){
                // 다음 방문할 정점의 거리를 현재 정점까지의 거리 +1이됩니다.
                check[next] = check[node] + 1;
                q.push(next);
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);

    // 1. 간선의 정보를 입력받으면서 양방향 그래프로 만들어줍니다.
    for(int i=0; i<m; i++){
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }

    // 2. 시작 정점을 거리를 1로 체크하고, BFS 탐색을 시작합니다.
    check[1] = 1;
    bfs(1);

    // 3. 시작 정점을 1로 체크했기 때문에 거리가 3이하인 정점만 개수에 더해 줍니다.
    // check[i] = 0이면 방문할 수 없는 정점입니다. check[i] = 1이면 시작 정점입니다.
    result = 0;
    for(int i=2; i<=n; i++){
        if(check[i] == 2 || check[i] == 3){
            result++;
        }
    }

    // 4. 결과 출력
    printf("%d\n", result);
}

2. python3

import sys, collections
input = sys.stdin.readline
print = sys.stdout.write

# 시간 복잡도: O(n+m)
# 공간 복잡도: O(m)
# 사용한 알고리즘: BFS
# 사용한 자료구조: 인접 리스트


def bfs(start):
    q = collections.deque()
    q.append(start)

    while q:
        node = q.popleft()

        for next in v[node]:
            if check[next] == 0:
                # 다음 방문할 정점의 거리를 현재 정점까지의 거리 +1이됩니다.
                check[next] = check[node] + 1
                q.append(next)


n = int(input())
m = int(input())

# 간선의 정보를 저장할 인접 리스트입니다.
v = [[] for _ in range(n+1)]

# 시작 정점으로 부터의 거리 정보를 담을 리스트입니다.
check = [0] * (n+1)


# 1. 간선의 정보를 입력받으면서 양방향 그래프로 만들어줍니다.
for _ in range(m):
    a, b = map(int, input().split())
    v[a].append(b)
    v[b].append(a)


# 2. 시작 정점을 거리를 1로 체크하고, BFS 탐색을 시작합니다.
check[1] = 1
bfs(1)


# 3. 시작 정점을 1로 체크했기 때문에 거리가 3이하인 정점만 개수에 더해 줍니다.
# check[i] = 0이면 방문할 수 없는 정점입니다. check[i] = 1이면 시작 정점입니다.
result = 0
for i in range(2, n+1):
    if check[i] == 2 or check[i] == 3:
        result += 1


# 4. 결과 출력
print("%d\n" % result)

3. java(openJDK)

import java.util.*;

// 시간 복잡도: O(n+m)
// 공간 복잡도: O(m)
// 사용한 알고리즘: BFS
// 사용한 자료구조: 인접 리스트

public class Main {

    static int n, m, a, b, result;
    static ArrayList<Integer>[] v = new ArrayList[501];
    static int[] check;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for(int i=1; i<=n; i++){
            v[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            a = sc.nextInt();
            b = sc.nextInt();
            v[a].add(b);
            v[b].add(a);
        }

        check = new int[n+1];

        check[1] = 1;
        bfs(1);

        result = 0;
        for(int i=2; i<=n; i++){
            if(check[i] == 2 || check[i] == 3){
                result++;
            }
        }

        System.out.println(result);
    }

    public static void bfs(int start){
        Queue<Integer>  q = new LinkedList<>();
        q.offer(start);

        while(!q.isEmpty()){
            int node = q.poll();

            for(int next:v[node]){
                if(check[next] == 0){
                    check[next] = check[node] + 1;
                    q.offer(next);
                }
            }
        }
    }

}