문제 보러 가기
문제
상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이의 동기의 수 n $$(2 ≤ n ≤ 500)$$이 주어진다. 둘째 줄에는 리스트의 길이 m $(1 ≤ m ≤ 10000)$이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 $a_i$ $b_i$가 주어진다. $(1 ≤ a_i < b_i ≤ n)$ $a_i$와 $b_i$가 친구라는 뜻이며, $b_i$와 $a_i$도 친구관계이다.
출력
첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.
예제 입력 1
6
5
1 2
1 3
3 4
2 3
4 5
예제 출력 1
3
예제 입력 2
6
5
2 3
3 4
4 5
5 6
2 5
예제 출력 2
0
힌트
예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대한다.
처음 딱 봤을때, 문제를 이해하지 못하였다. 그러나 힌트를 보고 이해하였다.
요점은 상근이의 친구와 친구의 친구만 초대하는 것이다. 즉, 친구가 아니거나 친구의 친구가 아닌사람, 다시말해 친구의 친구의 친구는 초대하지 않는다.
문제를 이해하고 나서 이걸 굳이 BFS나 DFS로 풀어야하나? 라는 생각이 들었고 그냥 직관적으로 풀어서 맞췄다.
그러나 그래프문제이고 BFS나 DFS로 풀수 있는 방법을 생각하여 몇개의 방법으로 풀어보았다.
직관적으로 푼 방법
import sys
from collections import deque
if __name__=="__main__":
n=int(input()) # 상근이 동기 수 1부터 n까지
m=int(input()) # 리스트의 길이
relation=[[] for _ in range(n+1)]
for _ in range(m):
a,b=map(int, input().split())
relation[a].append(b)
relation[b].append(a)
res=[]
for friend in relation[1]: # 상근이와 연결된 친구를 먼저 본다
res.append(friend) # 상근이 친구를 넣고
res += relation[friend] # 상근이 친구의 친구를 넣는다
ans = list(set(res)) # 중복을 제거한다
if len(ans)==0:
print(len(ans))
else:
print(len(ans)-1) # 상근이 자신은 빼준다.
BFS로 푸는 경우를 두가지 생각해 보았다
BFS로 푼 코드 1
import sys
from collections import deque
sys.stdin=open('input.txt', 'r')
if __name__=="__main__":
n=int(input()) # 상근이 동기 수 1부터 n까지
m=int(input()) # 리스트의 길이
relation=[[] for _ in range(n+1)]
visited=[0 for _ in range(n+1)]
for _ in range(m):
a,b=map(int, input().split())
relation[a].append(b)
relation[b].append(a) # 직접 친구간의 관계를 정의한다
cnt=0 # 부를 친구수
Q=deque()
Q.append([1,0]) # 시작인 상근이 1과 연결점을 정보로 넣음
visited[1]=1
while Q:
v,r=Q.popleft()
if r<=2: # 연결관계가 상근(0), 친구(1) 또는 친구의 친구(2)인 경우만
cnt+=1
for friend in relation[v]: # 사람과 관계된 친구
if visited[friend]==0:
visited[friend]=1 # 방문 기록하고
Q.append([friend,r+1]) # 그 사람과의 관계를 +1로 업데이트
print(cnt-1) # 상근이 자신은 빼줌
BFS로 푼 코드 2
import sys
from collections import deque
if __name__=="__main__":
n=int(input()) # 상근이 동기 수 1부터 n까지
m=int(input()) # 리스트의 길이
relation=[[] for _ in range(n+1)]
visited=[0 for _ in range(n+1)]
for _ in range(m):
a,b=map(int, input().split())
relation[a].append(b)
relation[b].append(a)
cnt=0
Q=deque()
Q.append(1)
visited[1]=1
while Q:
v=Q.popleft()
for friend in relation[v]:
if visited[friend]==0: # 첫 방문
Q.append(friend)
visited[friend]=visited[v]+1 # 방문지에 관계를 업데이트
res=0
for i in range(2,n+1): # 상근이는 제외라서 2부터 시작
if visited[i]<=3 and visited[i]!=0: # 본인이거나, 친구이거나, 친구의 친구인 경우면서 한번이상 방문한 경우
res+=1
print(res)
