[BOJ][⚪2][백준#05567] 결혼식

문제 출처

BAEKJOON Online Judge #5567

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

예제

예제 1

입력

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

출력

3

예제 2

입력

6
5
2 3
3 4
4 5
5 6
2 5

출력

0

My Sol

N = int(input())
M = int(input())
arr = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    arr[a].add(b)
    arr[b].add(a)

S = arr[1]
for s in arr[1]:
    S = S | arr[s]

if 1 in S: S.remove(1)
print(len(S))

정석적으로는 그래프를 이용하는 문제였지만, 해시를 사용해도 쉽게 풀 수 있는 문제였다.

1. 입력을 처리해준다.
2. 학번이 1번인 상근이의 지인(arr[1])들을 기본으로 둔다.
3. 각 지인들(s)의 지인들(arr[s])을 한 데 모은 합집합 S를 수집한다.
4. S에 1이 있다면 제거한다. 자기 자신이기 때문이다.
5. S의 길이를 출력한다.

결과

맞았습니다!!