본문 바로가기

BAEKJOON/구현

백준 10864번 [친구](C++) -yes6686- 티스토리

728x90
반응형
SMALL

백준 문제 풀이: 10864 (친구)


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

문제 설명:

도현이네 반에 N명의 학생이 있으며, M개의 친구 관계가 입력된다. 친구 관계는 양방향이며, 같은 쌍이 중복되거나 자기 자신과의 관계는 없다.

각 학생이 가지고 있는 친구의 수를 계산하여, 1번부터 N번 학생까지 한 줄씩 출력하라.


문제 해결 코드


// 10864번: 친구
// 각 학생의 친구 수를 계산하여 출력하는 문제

#include <iostream>
using namespace std;

int arr[1001];  // 학생 번호별 친구 수 저장 배열

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

    int n, m;
    cin >> n >> m;

    // 친구 관계 입력 처리
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        arr[a]++;  // a와 b는 친구
        arr[b]++;  // b와 a도 친구 (양방향)
    }

    // 학생 번호 1번부터 n번까지 출력
    for (int i = 1; i <= n; i++) {
        cout << arr[i] << '\n';
    }
}

코드 설명

  • 핵심 알고리즘: 간선 정보를 기반으로 각 정점(학생)의 차수(Degree)를 계산
  • 구현 세부사항:
    • arr[a]++, arr[b]++로 친구 수 증가
    • for (int i = 1; i <= n; i++)에서 1번부터 N번 학생까지 순차 출력
  • 시간 복잡도 분석:O(m) — 간선 수 만큼의 입력 처리총 시간 복잡도: O(n + m)
  • O(n) — 출력 처리

결과

각 학생의 친구 수를 출력합니다. 예를 들어:

예시 입력:
4 3
1 2
2 3
4 2

예시 출력:
1
3
1
1

2번 학생은 1, 3, 4와 친구라서 3명과 연결되어 있습니다.

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

728x90
반응형
LIST