[백준 / Python] #5567 결혼식

문제

 

https://www.acmicpc.net/problem/5567

5567번: 결혼식

---

Algorithm

문제에서 상근이의 친구와 친구의 친구를 초대한다고 하였으므로 bfs나 dfs를 상근이를 기준으로 1번한 후에 상근이와 연결된 간선만 탐색하면 되는 문제이다. 

문제에서 제시된 입력을 토대로 graph배열을 만들고, 1을 기준으로하여 탐색후 invited배열에 적용한다. 그 후에 1과 연결된 정점을 탐사한 후에 탐색을 종료한다. 이때, 1도 탐사를 하여 1이 된 상황이므로 출력을 할때는 invited배열에서 1의 개수에서 1(자기 자신)을 빼준 값을 출력해 주면 된다.

이때, 예제 입력2와 같이, 1과 연결된 간선이 없는 경우에는 초대할 사람이 없으므로 0을 출력하도록 한다.

---

 

 

Code

input = __import__('sys').stdin.readline

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

graph = [[] for i in range(n+1)]
invited = [0]*(n+1)

for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in graph[1]:
    invited[i] = 1
    for x in graph[i]:
        invited[x] = 1

if max(invited) == 0:
    print(0)
else:
    print(sum(invited)-1)