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
'BAEKJOON > 구현' 카테고리의 다른 글
백준 15235번 [Olympiad Pizza](C++) -yes6686- 티스토리 (0) | 2025.06.13 |
---|---|
백준 31458번 [!!초콜릿 중독 주의!!](C++) -yes6686- 티스토리 (1) | 2025.06.09 |
백준 11094번 [꿍 가라사대](C++) -yes6686- 티스토리 (2) | 2025.06.05 |
백준 12760번 [최후의 승자는 누구?](C++) -yes6686- 티스토리 (0) | 2025.06.04 |
백준 10163번 [색종이](C++) -yes6686- 티스토리 (0) | 2025.06.03 |